Cahpter 5. Binary Tree

Cahpter 5. Binary Tree#

Terminology

  • traversal order: the order of the nodes generated from a given traversal direction.

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

Traversal#

Preorder#

def preorder(root):
    # base case
    if not root:
        return []

    # store node 
    order = [root.val]
    # traverse the left subtree and right subtree
    order.extend(preorder(root.left))
    order.extend(preorder(root.right))
    
    # return
    return order

Inorder#

def inorder(root):
    # base case
    if not root:
        return []
    # store node 
    order = []
    # traverse the left subtree and right subtree
    order.extend(inorder(root.left))
    order.extend([root.val])
    order.extend(inorder(root.right))
    
    # return
    return order

Build#

A binary tree can be built from its given preorder, inorder and postorder traversal, or its serialization format directly.

From Preorder and Inorder#

From Postorder and Inorder#

From Preorder and Postorder#

From Preorder Serialization#

A binary tree can be directly built from a serialized representation of the original binary tree.

# because the serialization is preordered, we can do preorder traversal, to 
def buildFromPreorderSerialization(serialization):
    ss = serialization.split(',')

    def traverse():
        
        node = ss.pop(0)
        if node == "null":
            return None
        
        # do preorder
        node = Node(int(node))
        node.left = traverse()
        node.right = traverse()
        
        return node
    
    return traverse()

# test
s = '1,2,null,null,3,4,null,null,5,null,null'
tree = buildFromPreorderSerialization(s)
print(preorder(tree))
print(inorder(tree))

[1, 2, 3, 4, 5]
[2, 1, 4, 3, 5]

From Level Order Serialization#

def buildFromLevelOrderSerialization(s):
    ss = s.split(',')
    l = 0

    # define a level order traverse helper function
    pass
Contents