current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote -1 down vote favorite 
class BinaryTreeNode {

  private BinaryTreeNode left;
  private BinaryTreeNode right;
  private int data;

  BinaryTreeNode(int d) {
    data = d;
  }

  public void insertLeft(BinaryTreeNode n) {
    this.left = n;
  }

  public void insertRight(BinaryTreeNode n) {
    this.right = n;
  }

  public int height() {
    // height = Max(Hl, Hr) + 1
    int leftHeight = this.left != null ? left.height() : -1;
    int rightHeight = this.right != null ? right.height() : -1;
    return Math.max(leftHeight, rightHeight) + 1;
  }

  public String toString() {
    String leftStr = this.left == null ? "" : this.left.toString();
    String rightStr = this.right == null ? "" : this.right.toString();
    return leftStr + " : " + data + " : " + rightStr;
  }

  public static void main(String[] s) {
    BinaryTreeNode n  = new BinaryTreeNode(0);//             0         l0
                                              //            / \
    BinaryTreeNode l1 = new BinaryTreeNode(1);//           1   4       l1
                                              //          /
    BinaryTreeNode l2 = new BinaryTreeNode(2);//         2             l2
                                              //        /
    BinaryTreeNode l3 = new BinaryTreeNode(3);//       3               l3
    l2.insertLeft(l3);
    l1.insertLeft(l2);
    n.insertLeft(l1);
    n.insertRight(new BinaryTreeNode(4));
    System.out.println(n.height());
    System.out.println(isBalanced(n));
  }

  public static boolean isBalanced(BinaryTreeNode n) {
    // if height = (|hl - hr|) <=1
    int leftHeight = n.left != null ? n.left.height() : -1;
    int rightHeight = n.right != null ? n.right.height() : -1;
    return leftHeight - rightHeight <= 1;
  }
}
share|improve this question
    
The insertLeft and insertRight methods only store the new nodes, but there is not strategy to determine if the node is supposed to go in which direction. –  Lloyd Moore Apr 28 at 13:19
    
@LloydMoore - I presume the logic for adding nodes is not part of the review, just whether the isBalanced and height... although, I agree that it would be nice to see more about how the data is loaded. It is possible that this is a pre-cursor to creating an always-balanced tree. –  rolfl Apr 28 at 13:25
    
In addition, the code that implements BinaryTreeNode should also be added.... without it there's only a partial picture of what's happening. –  rolfl Apr 28 at 13:27
    
@rolfl I take your point, however, from the title it is hard to make assumptions otherwise. If that is the case, then I would advise the question is annotated as such. Isn't the main() method the implementor of the class? Just reinforcing the point about assumptions and probable missing code to give a proper review. –  Lloyd Moore Apr 28 at 13:54
    
@LloydMoore - sometime the obvious escapes me. Yes, I missed that the class itself was the node... hmm. That's ... embarassing. –  rolfl Apr 28 at 13:56

2 Answers 2

up vote 0 down vote

Instead of having a method to calculate the heights of the subtrees or a method to check whether the tree is balanced, I suggest just storing the depth of a node in that node. Then when a node is added or removed – which at most will change the subtree depth by 1 – just update the node depths of each parent node out to the root, short-circuiting when you've reached a point where the depth doesn't change.

This should non-trivially reduce the runtime complexity of balancing the tree. This, of course, comes at the cost of a little more storage space.

Then your algorithm for adding a node would be:

  1. Find the location in the tree where the new node belongs
  2. Add the node and start backing out of the tree.

  3. At each node on the way out...

    A. Check if the current subtree is balanced.

    • If it's a leaf node, there's nothing to do
    • A balanced subtree has a difference <1 between the depths of its right and left subtrees

    C. If the current subtree is not balanced, balance it with a tree rotation.

    B. Update the depth of the current subtree.

    • The depth is the greater of the two subtrees' depths plus 1

    C. Stop backing out of the tree if at any point the depth of the current subtree did not change.

This should give you a complexity of O(log n) for adding/deleting nodes because it touches only one branch of the tree. Your current solution of checking the height has a complexity of O(n) because you recursively touch every node.

Note: this solution also requires you to store a pointer for each node's parent node (for use in backing out of the tree), which you don't have in the code you originally posted.

share|improve this answer
    
It would cost more than just storage space, it would also require remembering the path-to-the-inserted-node and backtracking it to update the depth. The alternate algorithm also creates an always-balanced tree, which is very different to checking for a possibly balanced one. –  rolfl Apr 28 at 17:11
    
@rolfl No, it wouldn't require remembering anything. All of the steps in the algorithm I described should be done at once. So you traverse the tree out the destination node, and then you reverse course. Did you not include a pointer for a node's parent? –  Sildoreth Apr 28 at 17:14
    
Ahh, I think that's the key difference in our thought processes. I agree that you should, if you need a balanced tree, always keep it balanced. Every operation should require a stable and balanced result. On the other hand, this question assumes the opposite. There is no need to maintain a balanced tree, just to get an indication of whether it is balanced, or not. –  rolfl Apr 28 at 17:18
    
Also, I don't see the point of creating a maybe-balanced tree. Either you want it balanced, or you don't. And you don't gain anything by building up a completely UN-balanced tree and then balancing it after the fact. In fact, that would give you significantly worse performance because finding where a value belongs in the tree when you are inserting would then have an upper bound of O(n). –  Sildoreth Apr 28 at 17:18
up vote 1 down vote

Your question is unclear, though I can tell that your code is broken.

Your code here:

  public static boolean isBalanced(BinaryTreeNode n) {
    // if height = (|hl - hr|) <=1
    int leftHeight = n.left != null ? n.left.height() : -1;
    int rightHeight = n.right != null ? n.right.height() : -1;
    return leftHeight - rightHeight <= 1;
  }

Should return true if the tree is balanced, but, it takes a node in, computes the height of the left and right sides, and compares the differences.

This method is broken.... Just because the height of each side of the tree (left, and right) are similar, does not mean that each side is also balanced. Consider a tree like:

    //             0
    //            / \
    //           1   4
    //          /   /
    //         2   5
    //        /   /
    //       3   6

When you test the root, you will determine that both sides have the same height, yet, the tree is far from balanced.

share|improve this answer
    
Oops, I missed it totally. I see that @Sildoreth gave a nice solution I will check that out. –  CodeYogi Apr 28 at 17:07
    
Also, one small advice if you don't mind. What do you do when you fumble on problem like these? should I try to solve them with pen and paper first before jumping in or I should directly code and do quick iterations to reach the solution? I am newbie so your advice can help me for lifetime, thanks :) –  CodeYogi Apr 28 at 17:10
1  
@CodeYogi - Test data, and debugging. I strongly recommend that you sit down and "imagine" a set of scenarios to test, and build tests that implement them. Then make sure that your code makes all the tests work. Add more tests as you go on. This is called "TDD". Once you get in to it, between that, and your debugger, you will discover that you have to plan ahead a little bit, you have a benchmark to measure your progress against, and you have a goal to drive for, and you know when you meet it. –  rolfl Apr 28 at 17:16
    
ya, I try to do that sometimes but I am not consistent. I think I should stick to this methodology for a longer time because it requires a lots of patience and practice. Thanks! –  CodeYogi May 5 at 4:23

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.