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 every node never differ by more than 1.

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

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: int height(TreeNode *root){ if(root == NULL){ return 0; } int leftHeight = height(root->left); if(leftHeight == -1){ return -1; } int rightHeight = height(root->right); if(rightHeight == -1){ return -1; } if(abs(leftHeight - rightHeight) > 1){ return -1; } return 1 + max(leftHeight, rightHeight); } bool isBalanced(TreeNode* root) { if(root == NULL){ return true; } if(height(root) == -1){ return false; } return true; } };

Read More

104. Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node. Height of empty binary tree is 0 and with just root node is 1.

                                    1
                                 /     \
                                2       3
                                 \
                                  5

For the above example, the maximum depth is 3 following the path 1-2-5.

Approach : Using the recursive approach as implemented below.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ int max(int a, int b){ return a >= b ? a : b; } int maxDepth(struct TreeNode* root) { int height; //base case if(root == NULL){ return 0; } //recursively compute left and right height and return the maximum height = 1 + max(maxDepth(root->left), maxDepth(root->right)); return height; }

Read More

100. Same Tree

Given two binary trees, write a function to check if they are equal or not. 

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.
Below are some examples:

Ex. 1:
Tree 1:
                   10
        20                   30
  40        50        60        70

Tree 2:    
                  10
        20                   30
  40        50        60        70
Tree 1 & Tree 2 are identical.

Example 2:
Tree 1:    
                 10
        20                   30
  40        50        60        70
Tree 2:
                   10
        20                   30
  40        60        50        70

Trees 1 & 2 are not identical as their structures are same but values at nodes 50 and 60 differ.

Example 3:
Tree 1:
                   10
        20                   30
  40        50        60        
Tree 2:
                   10
        20                   30
  40        50                  60

Trees 1 & 2 are not identical as the structures are not same as 60 is on left subtree of node 30 in Tree 1 but on right subtree of node 30 in Tree 2.

Approach : Use the simple recursive solution.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ bool isSameTree(struct TreeNode* p, struct TreeNode* q) { if(p == NULL && q == NULL){ return true; } if(p == NULL && q != NULL || p != NULL && q == NULL){ return false; } if(p->val == q->val){ return isSameTree(p->left, q->left) && isSameTree(p->right, q->right); } return false; }

Read More

Invert Binary Tree

Invert a binary tree.
For example, convert

     4
   /   \
  2     7
 / \   / \
1   3 6   9

to

     4
   /   \
  7     2
 / \   / \
9   6 3   1

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

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: void invert(TreeNode *root){ TreeNode *temp; temp = root->left; root->left = root->right; root->right = temp; if(root->left){ invert(root->left); } if(root->right){ invert(root->right); } } TreeNode* invertTree(TreeNode* root) { if(root == NULL){ return NULL; } invert(root); return root; } };

Read More

Lowest Common Ancestor of a Binary Tree

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

 /**  
  * Definition for a binary tree node.  
  * struct TreeNode {  
  *   int val;  
  *   TreeNode *left;  
  *   TreeNode *right;  
  *   TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
  * };  
  */  
 class Solution {  
 public:  
   TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {  
     if(root == NULL){  
       return NULL;  
     }  
     if(root == p || root == q){  
       return root;  
     }  
     TreeNode *left = lowestCommonAncestor(root->left, p, q);  
     TreeNode *right = lowestCommonAncestor(root->right, p, q);  
     if(left != NULL && right != NULL){  
       return root;  
     }  
     if(left == NULL && right == NULL){  
       return NULL;  
     }else{  
       return left != NULL ? left : right;  
     }  
   }  
 };      

Read More