Solution by ppalit


  • 0
    P

    Approach #1 Recursive

    Intuition

    Traverse the BST recursively and count depth of left and right subtree. The higher value should be teh deplth of the tree

    Algorithm

    If the root is null then the depth is 0.
    else recursively traverse the left node
    similarly traverse the right node
    return the greater of the left or right node every time incrementing it.

    Java

    class Solution {
        public int maxDepth(TreeNode root) {
          if (root == null) {
            return (0); 
          } else {
            int leftDepth = maxDepth(root.left);
            int rightDepth = maxDepth(root.right);
            if (leftDepth > rightDepth )
                return (leftDepth+1);
            else
                return (rightDepth+1);
            }
        }
    }
    

    Complexity Analysis

    • Time complexity : O(n).

    Since it require traversal of all the nodes of the tree , complexity is equal to the worst case traversal of a BST search which is O(n)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.