Welcome to the new Binary Tree Series. In, this new series we will learn about Binary Trees as part of Data Structures and Algorithms. The Pre-requisites to get started with Binary Tree is to know about Recursion. Recursion is the Heart and Soul of Binary Tree. Now to get comfortable with the Binary Tree and Recursion, we will now start with easy problems of the Binary Tree. Binary Tree is Very Important to Land a Job in Big Tech Companies Like Google, Facebook, Amazon, and Microsoft. There will be at least one question asked either in Coding Round or In the Interview. Since our Main Aim of this New Series is to get placed in those Big Tech Companies, we need to Ace Binary Tree's Concept. With that said, Let's Begin Our First Problem of Leetcode which is to Find the Maximum Depth of the Binary Tree.
Approach:
Example 1:
Input: root = [3,9,20,null,null,15,7] Output: 3
Let's Take the Example of the above Binary Tree. As we know that Parent Node is the Root Node of the Binary Tree. In the above case, the root node is 13. The Below Left and Right Nodes are the Child Nodes. If there are no Nodes either on the Left or Right, then we treat it as Null. Now to Find the Maximum Depth of the Binary Tree, we need to Traverse both on the Left and the Right. If there is no Left Node and Right Node to the Parent Node, then we simply return the Parent Node. Since we know that it is Not Null in the above example, We now Traverse on the Left of Parent Node. The result comes out to be 1 from the Left Part of the Binary Tree. The Result of the Left Part is stored in a Variable Known as 'left'. We now Traverse on the Right Part of Parent Node. The result comes out to be 2 from the Right Part of the Binary Tree. The Result of the Right Part is stored in a Variable Known as 'right'. Now our Last Task is to Find the Maximum of 'left' and 'right' variables and add '1' to include the Parent Node to the Result. So the Final Answer Comes out to be '3'. The Complexity of the Below Code is O(n).
Code:
class Solution {
public int maxDepth(TreeNode root) {
if(root == null)
return 0;
int left = maxDepth(root.left);
int right = maxDepth(root.right);
int res = Math.max(left, right) +1;
return res;
}
}
Example 2:
Input: root = [1,null,2] Output: 2
0 Comments