DAY 56 - Binary Tree Questions(I)

Welcome to DAY 56. Today we will diverge once again into the Data Structure Trees and look at some more traversals. I suggest reading the previous article on Trees before reading this.

Questions:

Maximum Depth of Binary Tree:

Given the root of a binary tree, return its maximum depth.

A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Example 1:

• Input: root = [3,9,20,null,null,15,7]
• Output: 3

Algorithm and Code:

• So the question is basically asking us to find the height of binary tree.
• What's the height of a binary tree? It is the maximum level you can go to in the furthest leaf node.
• In our example we see 15 and 7 are the farthest from the root node.
• They are both at a height of 3.
• So We look at this in a recursive way, We don't need to find out the totalHeight. We can just find the max height bw Left and Right subtree and we can add 1 to that as the final node is root node.
• If you imagine this we can apply similar logic to left subtree's left subtree and so on and similarly for right subtree.
• Hence by using this logic we can find out max depth using this recursive approach.

int maxDepth(TreeNode* root) { if(root == NULL) { return 0; } int lh = maxDepth(root->left); int rh = maxDepth(root->right); return 1 + max(lh,rh); } 

Question: Balanced Binary Tree

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

A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

Example 1:

• Input: root = [3,9,20,null,null,15,7]
• Output: true

Naïve Approach:

• We can either checkout the height at every node of the tree.
• If we find the absolute difference to be greater than 1 we return false.
• We use the code above to find the height of the subtrees and then We recursively check to find if each node is balanced.
• This is a good approach but we are taking a Time Complexity of O(n^2) to find our result as we are finding height in o(N) time for every node and traversing every node also takes O(N) time.
• This approach is not time efficient.

Code:

int maxDepth(TreeNode* root) { if(root == NULL) { return 0; } int lh = maxDepth(root->left); int rh = maxDepth(root->right); return 1 + max(lh,rh); } bool isBalanced(TreeNode* root) { // base case if(root == NULL) { return true; } bool lb = isBalanced(root->left); bool rb = isBalanced(root->right); bool diff = abs(maxDepth(root->left) - maxDepth(root->right)) <= 1; if(lb && rb && diff) { return true; } else { return false; } } 

Complexity Analysis:
Time: O(N^2)
Space: O(1)

Better Approach:

• Instead of returning a height from our getHeight function or maxDepth function.
• How about we instead only get height if they are balanced.
• In the maxDepth function we are traversing the whole array anyway using the same logic.
• When we are finding the heights of left and right subtree of the node, why not instead of continuing we simply keep returning -1 which indicates it's not balanced.
• It removes the redundancy and also helps us out by optimizing the time.

Code:

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

Complexity Analysis:
Time: O(N)
Space: O(1)