## Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of

*eve**ry*node never differ by more than 1.### Analysis:

Note here is slightly different from the Cracking the Code Interview 4.1, one can notice that the code from 4.1 will not pass all the test samples here. That is because the definition of balanced. In 4.1, balanced is defined by all the node differs in depth less than or equal to 1. But here balanced is defined the difference of max depth of left tree and right tree are less than or equal to 1.The key idea is from the 4.1, where compute the max and min depth of the whole tree and see the difference. Here, we compute the max depth of two sub tree of a node, if the difference is > 1, output false.

The source code of Cracking the Code Interview 4.1 :

/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: int maxDepth(TreeNode * root){ if (root==NULL){return 0;} return 1+max(maxDepth(root->left),maxDepth(root->right)); } int minDepth(TreeNode * root){ if (root==NULL){return 0;} return 1+min(minDepth(root->left),minDepth(root->right)); } bool isBalanced(TreeNode *root) { // Start typing your C/C++ solution below // DO NOT write int main() function int maxd = maxDepth(root); int mind = minDepth(root); if (abs(maxd-mind)<=1) {return true;} else {return false;} } };

### Code(C++) :

/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: int maxDepth(TreeNode * root){ if (root==NULL){return 0;} return 1+max(maxDepth(root->left),maxDepth(root->right)); } bool testNode(TreeNode * root){ if (root==NULL) {return true;} if (abs(maxDepth(root->left) - maxDepth(root->right)) >1) {return false;} return (testNode(root->left) && testNode(root->right)); } bool isBalanced(TreeNode *root) { // Start typing your C/C++ solution below // DO NOT write int main() function return testNode(root); } };

### Code(Python):

# Definition for a binary tree node # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: # @param root, a tree node # @return a boolean def maxd(self, root): if root == None: return 0 else: return 1 + max(self.maxd(root.left), self.maxd(root.right)) def testNode(self, root): if root == None: return True else: if abs(self.maxd(root.left) - self.maxd(root.right)) > 1: return False else: return self.testNode(root.left) and self.testNode(root.right) def isBalanced(self, root): return self.testNode(root)

This comment has been removed by the author.

ReplyDeleteIsn't calling both maxDepth and testNode on every node very inefficient? Wouldn't this traverse every node the same number as its height instead of just once?

Deletewrong answer

ReplyDeleteIn the c++ code in function testNode you need to put an else condition before the return, because if abs value is greater than 1 you should not again go into it.

ReplyDelete