MAX DEPTH OF BINARY TREE

By: Saurav

2018-01-17 23:22:00 UTC

Given a binary tree, find its maximum depth.

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

NOTE : The path has to end on a leaf node.
Example :

1
/
2
max depth = 2.

InterviewBit

If you know recursion, and you know binary trees, this problem would be simple.

Algo:
Base case: if root if nil, return 0 and if root has no children, return 1
Otherwise: return the maximum of left and right subtree depth + 1

One way:

def maxDepth(a)
        return 0 if !a
        return 1 if !a.left and !a.right
        
        return [maxDepth(a.left), maxDepth(a.right)].max + 1

    end

Another way:

def maxDepth(a)
        return 1 if !a.left and !a.right
        return [ a.left ? maxDepth(a.left) : 0, a.right ? maxDepth(a.right) : 0].max + 1
    end

Looks good to me.


Let me know what you think!
twitter: sprakash24oct
linkedin

Owned & Maintained by Saurav Prakash

If you like what you see, you can help me cover server costs or buy me a cup of coffee though donation :)