CODEWITHSUNDEEP
javabinary-treetree-traversal
Tsundoku
Tsundoku

Reputation: 9418

Tree traversal in Java

I am studying for a job interview and was reviewing trees, I have no problem when traversing them but I got to a question I haven't been able to figure the right answer to:

Write a function that returns a node in a tree given two parameters: pointer to the root node and the inorder traversal number of the node we want to return. The only information stored in the tree is the number of children for each node.

So far, I haven't even been able to figure why I would care of the information stored in the tree (the number of children). Other than that if we assume there's a tree like such:

     5
  4     7
3  1  4

then the Inorder traversal would be 341547but I can't figure out the code to return the node I want (for sake of argument I'm assuming the inorder traversal number is 2 - meaning I want the node of value 1).

I tried doing a recursive traversal but I end up screwing the inner counter I had so I tried a different approach and just tried to put everything on a stack but I can't figure how to correctly do so. So far I have:

public int findNode(root, position){
   Stack<Integer> s = new Stack<Integer>();
   cNode = root; //cNode = current Node

   while(cNode.left != null)
      cNode = cNode.left;

     s.push(cNode);

   while(cNode.right != null)
     cNode = cNode.right;

   //stuck here.
}

The recursive approach was easier but I can't figure how to check if I have the # I'm looking for:

public int findNode(root, position){
    cNode = root;   
    if(cNode != null){ 
       findNode(cNode.left, position);
       System.out.print(cNode.data);
       findNode(cNode.right, position);
   }
}

I know this traverses the tree but it still doesn't do exactly what I want. Any help would be appreciated.

Upvotes: 1

Views: 11103

Answers (4)

mayank_hey
mayank_hey

Reputation: 166

It is better to reduce the complexity of the algorithm by using the property of the tree that each node knows the total number of children it has. So you can calculate the order number of the current node if you know how many children it has on the left (for root it will be no. of children on left + 1) The following code should work:

Nodeptr nthInInorder(Nodeptr root, int x){
 Nodeptr curr = root;
 int countedIn = 0, leftchildren = 0, currIn=0;

 while(curr!=NULL){
  if(curr->left == NULL)
   leftchildren = 0;
  else
   leftchildren = (curr->left)->data + 1;

  currIn = countedIn + leftchildren + 1;

  if(currIn == x)
   return curr;
  else if(currIn > x)
   curr = curr->left;
  else if(currIn < x)
   { countedIn = currIn + 1;
     curr = curr->right;
   }
  }
  return NULL;
 }

Complexity of this algorithm is O(log n)

Upvotes: 0

Daniel Moses
Daniel Moses

Reputation: 5858

You can do it as such: 

public Node findNode(Node root, int position) {
    ArrayList<Node> a = new ArrayList<Node>();
    populateNodes(root, a);
    return a.get(position);
}

private void populateNodes(Node node, ArrayList<Node> a) {
    if (node == null) return;
    populateNodes(node.left, a);
    a.add(node);
    populateNodes(node.right, a);
}

Note: You don't need to use an extra data-structure if you don't want, but since you had a Stack i just went with it.

Note2: As Jim Garrison pointed out you can optimize the algorithm if you have the descendant count.

Upvotes: 1

Erik B
Erik B

Reputation: 2858

Instead of passing position, pass the inorder traversal number and append to it in each recursive method.

Upvotes: 0

Jim Garrison
Jim Garrison

Reputation: 86774

The question is ambiguous. "Inorder" is meaningful for binary trees, in which case "number of children" is always two, unless they mean "number of descendants", in which case you could use that to avoid doing a linear search through the inorder list (O*n) since at each node you can decide which branch to take (O*log n) based on the number of descendants.

Upvotes: 1

Related Questions