committedandroider committedandroider - 4 years ago 214
Java Question

How to continue shifting the root when you have to add nodes to the end(binary trees construct)?

this is not a homework question. I'am practicing for an interview.
This is the problem description

Write a method construct that accepts an integer n as a parameter and that constructs a new tree of integers with n nodes numbered 0 through (n - 1) such that an in-order traversal of the tree will produce the values in sequential order. The tree should be balanced in that the number of values in any node's left subtree should always be within one of the number of values in its right subtree. If there is an extra value in one of a node's two subtrees, it should appear in the right subtree.

For example, given a variable tree of type IntTree, the call of tree.construct(7); should produce the first tree shown below. If the call had been tree.construct(10);, the tree's state should be that of the second tree shown below.

enter image description here

Assume that you are adding this method to the IntTree class as defined below:

public class IntTree {
private IntTreeNode overallRoot;
...
}

Here are my initial thoughts
the empty case is easy, you just make the node null. I see that for any n, you need to introduce a new node that has the value of n - 1. I also see that for all the odd ns, the overall Root shifts up by one. I dealt with the problem at the beginning by shifting the entire tree. (that is move the original root to the left, new root to overall Root). To do this you need constant access to overall Root. The problem is when I reach n = 4, I have to introduce a new node 3 to the right of a sub node of the overall node (means I lose access to the overall node). Is there a better way to do this(add and maintain access)?

Answer Source

There are several approaches, but the simplest to work out on the fly in an interview is recursive. For range [a,b] split it into [a,r-1], r, [r+1,b]. Then build a tree with r as the root and recursively build trees for the ranges, making their roots the children. The rest is to make sure the condition on missing children is met. This is just picking r carefully.

class InorderIntegerTree {

  Node root;

  static class Node {

    int val;
    Node left, right;

    Node(val, left, right) {
      this.val = val;
      this.left = left;
      this.right = right;
    }
  }

  Node make(int a, int b) {
    if (a > b) return null;
    int r = b + (b - a) / 2;
    return new Node(r, make(a, r-1), make(r+1, b));
  }

  InorderIntegerTree(int n) {
    root = make(0, n-1);
  }  
}
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download