Passing Balls: Easy Version

Computer Science Level 1

The binary search tree above has a height of 2 and has 4 leaves. You are going to pass down a ball from the root (the topmost node). Every node other than the leaves has a switch. If a node is switched off , the ball will pass to its left child; if a node is switched on , the ball will pass to its right child. After passing the ball, the switch will toggle (if it's on it becomes off and vice versa). Initially, every node is switched off.

Chris built a similar tree of height 3 with the same indexing. Which leaf will contain the 5 th 5^\text{th} ball?

Note : the indexes of the leaves should be in the range [ 8 , 16 ) [8,16) .

Do you find this too simple? Try the Medium version of this problem.


The answer is 9.

View wiki
Christopher Boo by Christopher Boo , 24, Singapore

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Pranjal Jain
Jun 2, 2016 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
 
#include<bits/stdc++.h>
#define ll          long long int
#define pb          push_back
#define mp          make_pair
#define pii         pair<int,int>
#define vi          vector<int>
#define Max(a,b)    ((a)>(b)?(a):(b))
#define Min(a,b)    ((a)<(b)?(a):(b))
#define rep(i,a,b)  for(int i=a;i<b;i++)
#define all(a)      a.begin(),a.end()
#define F           first
#define S           second
#define sz(x)       (int)x.size()
#define hell        1000000007
#define endl        '\n'

using namespace std;
struct Node{
    int val;
    int height;
    bool toggled;
    Node* left;
    Node* right;
};
Node* createNode(int height,int val=1){
    Node* temp=new Node;
    temp->height=height;
    temp->toggled=false;
    temp->val=val;
    if(height==0){
        temp->left=NULL;
        temp->right=NULL;
    }
    else{
        temp->left=createNode(height-1,val*2);
        temp->right=createNode(height-1,val*2+1);
    }
    return temp;
}
int traverse(Node* root){
    if(root->height==0){
        return root->val;
    }
    root->toggled=((root->toggled)^1);
    if(root->toggled){
        return traverse(root->left);
    }
    else{
        return traverse(root->right);
    }
}
void solve(){
    int h;
    cin>>h;
    Node* root=createNode(h);
    int num;
    cin>>num;
    int ans;
    rep(i,0,num){
        ans=traverse(root);
    }
    cout<<ans;
}

int main(){
    solve();
}

8 Helpful 4 Interesting 2 Brilliant 2 Confused

1 pending report

Vote up reports you agree with

×

Problem Loading...

Note Loading...

Set Loading...