Maximum Depth of Binary Tree

LeetCode

Commonly asked at:Amazon Google LinkedIn

Maximum Depth of Binary Tree

Given a binary tree, return its maximum depth (the number of nodes along the longest path from root to a leaf).

Example

Input (level-order, null for missing): 3 9 20 null null 15 7 Output: 3

Approach

The depth of a tree is 1 (for the root itself) plus the deeper of its two subtrees' depths — a two-line recursive definition. An empty tree has depth 0.

Input format

Line 1: the tree in level-order, space-separated, null for a missing child (this is LeetCode's own tree-input convention)

Print the maximum depth.

Not solved yet

Ctrl+Enter

Editor

# Tree is provided level-order with 'null' markers; build_tree() constructs it for you.
class TreeNode:
    def __init__(self, val=0):
        self.val = val
        self.left = None
        self.right = None

def build_tree(tokens):
    if not tokens or tokens[0] == 'null':
        return None
    root = TreeNode(int(tokens[0]))
    queue = [root]
    i = 1
    while queue and i < len(tokens):
        node = queue.pop(0)
        if i < len(tokens) and tokens[i] != 'null':
            node.left = TreeNode(int(tokens[i])); queue.append(node.left)
        i += 1
        if i < len(tokens) and tokens[i] != 'null':
            node.right = TreeNode(int(tokens[i])); queue.append(node.right)
        i += 1
    return root

tokens = input().split()
root = build_tree(tokens)
# TODO: depth(node) = 0 if node is None else 1 + max(depth(left), depth(right))

# Tree is provided level-order with 'null' markers; build_tree() constructs it for you.
class TreeNode:
    def __init__(self, val=0):
        self.val = val
        self.left = None
        self.right = None

def build_tree(tokens):
    if not tokens or tokens[0] == 'null':
        return None
    root = TreeNode(int(tokens[0]))
    queue = [root]
    i = 1
    while queue and i < len(tokens):
        node = queue.pop(0)
        if i < len(tokens) and tokens[i] != 'null':
            node.left = TreeNode(int(tokens[i])); queue.append(node.left)
        i += 1
        if i < len(tokens) and tokens[i] != 'null':
            node.right = TreeNode(int(tokens[i])); queue.append(node.right)
        i += 1
    return root

tokens = input().split()
root = build_tree(tokens)
# TODO: depth(node) = 0 if node is None else 1 + max(depth(left), depth(right))

Input (stdin)

Output

Run your code to see output here.

Isolated sandbox · not executed on your devicePowered by Judge0 CE (free, self-hosted). Runs in an isolated sandbox — not on your device.

Editor

# Tree is provided level-order with 'null' markers; build_tree() constructs it for you.
class TreeNode:
    def __init__(self, val=0):
        self.val = val
        self.left = None
        self.right = None

def build_tree(tokens):
    if not tokens or tokens[0] == 'null':
        return None
    root = TreeNode(int(tokens[0]))
    queue = [root]
    i = 1
    while queue and i < len(tokens):
        node = queue.pop(0)
        if i < len(tokens) and tokens[i] != 'null':
            node.left = TreeNode(int(tokens[i])); queue.append(node.left)
        i += 1
        if i < len(tokens) and tokens[i] != 'null':
            node.right = TreeNode(int(tokens[i])); queue.append(node.right)
        i += 1
    return root

tokens = input().split()
root = build_tree(tokens)
# TODO: depth(node) = 0 if node is None else 1 + max(depth(left), depth(right))

# Tree is provided level-order with 'null' markers; build_tree() constructs it for you.
class TreeNode:
    def __init__(self, val=0):
        self.val = val
        self.left = None
        self.right = None

def build_tree(tokens):
    if not tokens or tokens[0] == 'null':
        return None
    root = TreeNode(int(tokens[0]))
    queue = [root]
    i = 1
    while queue and i < len(tokens):
        node = queue.pop(0)
        if i < len(tokens) and tokens[i] != 'null':
            node.left = TreeNode(int(tokens[i])); queue.append(node.left)
        i += 1
        if i < len(tokens) and tokens[i] != 'null':
            node.right = TreeNode(int(tokens[i])); queue.append(node.right)
        i += 1
    return root

tokens = input().split()
root = build_tree(tokens)
# TODO: depth(node) = 0 if node is None else 1 + max(depth(left), depth(right))

Input (stdin)

Output

Run your code to see output here.

Isolated sandbox · not executed on your devicePowered by Judge0 CE (free, self-hosted). Runs in an isolated sandbox — not on your device.

Community Discussions

No discussions yet

Be the first to start a conversation.