Maximum Depth of Binary Tree

Sources: leetcode 105

Rating: medium

Given preorder and inorder traversal of a tree, construct the binary tree.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def buildTree(preorder: List[int], inorder: List[int]) -> TreeNode:
    # give binary tree

Solution

Initialize the head of the tree based on the preorder list, then set up an interation using two indices, i for the preoder and j for the inorder list.

def buildTree(preorder, inorder):
    if len(preorder) == 0:
        return None
    head = TreeNode(preorder[0])
    stack = [head]
    i = 1
    j = 0
    while i < len(preorder)
        # iterate through i, building tree
    return head

Use the stack to identify the next preorder and inorder node.

def buildTree(preorder, inorder):
    if len(preorder) == 0:
        return None
    head = TreeNode(preorder[0])
    stack = [head]
    i = 1
    j = 0
    while i < len(preorder)
        temp = None
        t = TreeNode(preorder[i])
        while stack and stack[-1].val == inorder[j]:
            temp = stack.pop()
            j += 1
        # add children
    return head

Finally, add the child nodes, extend the stack, and increment i.

Final Code

def buildTree(preorder, inorder):
    if len(preorder) == 0:
        return None
    head = TreeNode(preorder[0])
    stack = [head]
    i = 1
    j = 0
    while i < len(preorder)
        temp = None
        t = TreeNode(preorder[i])
        while stack and stack[-1].val == inorder[j]:
            temp = stack.pop()
            j += 1
        if temp:
            temp.right = t
        else:
            stack[-1].left = t
        stack.append(t)
        i += 1
    return head

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s