Binary Trees

Definition

class Node:
  def __init__(self, data):
    self.data = data
    self.left = None
    self.right = None
    
# create nodes
root = Node('A')
n1 = Node('B')
n2 = Node('C')
n3 = Node('D')
n4 = Node('E')

# setup children
root.left = n1
root.right = n2
n1.left = n3
n1.right = n4

( example and code src: codebyte)

• depth of node n: number of nodes on the search path from root to n, not including n itself.

• height of the tree: maximum depth of any node in the tree.

• full binary tree: all nodes other than leaves has two children
• perfect binary tree: every parent has two children
  • number of nodes in a perfect binary tree of height \(h\): \(2^{h+1}-1\)
  • number of leaves: \(2^{h}\)

Tree traversal

Binary search trees: left.data < root.data < right.data

• inorder: allows data arranged in order. left –> root –> right (左根右)
• preorder: root –> left –> right （根左右）
• postorder: left –> right –> root （左右根）
• level order: read level by level

Say we have binary tree of \(n\) nodes, height \(h\), for traversals:

• time complexity = \(O(n)\);
• space complexity = \(O(h)\).
  (Note: If each node has parent field, traversal can be done with space complexity \(O(1)\)).

Inorder traversal

def in_order(root, nodes):
    if root and root.left:     #inorder left subtree
        in_order(root.left, nodes)
    nodes.append(root.data)    #root
    if root and root.right:    #inorder right subtree
        in_order(root.right, nodes)
    return nodes

print in_order(root, []) # => ['D', 'B', 'E', 'A', 'C']

Preorder traversal

def pre_order(root, nodes):
    nodes.append(root.data)
    if root and root.left:
        pre_order(root.left, nodes)
    if root and root.right:
        pre_order(root.right, nodes)
    return nodes
print pre_order(root, []) # => ['A', 'B', 'D', 'E', 'C']

Postorder traversal

def post_order(root, nodes):
    if root and root.left:
        post_order(root.left, nodes)
    if root and root.right:
        post_order(root.right, nodes)
    nodes.append(root.data)  
    return nodes

print post_order(root, []) # => ['D', 'E', 'B', 'C', 'A']

Basically in the three blocks of codes, only nodes.append(root.data) changes its position.

Level order

• output a single array

    def level_order(root, nodes):
        queue = [root]
        while queue:
            n = queue.pop(0)
            nodes.append(n.data)
            if n.left:
                queue.append(n.left)
            if n.right:
                queue.append(n.right)
        return nodes
      
    print level_order(root, []) # => ['A', 'B', 'C', 'D', 'E']
  

  利用一个queue, 首先将root加入queue, 之后每次从queue中pop出一个将其左右子加入queue序列，将其data加入输出。

• output arrays level by level

    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
          
        res = []
        self.dfs(root, 0, res)
        return res
  
    def dfs(self, root, depth, res):
        if root == None:
            return res
        if len(res) < depth+1:
            res.append([])
        res[depth].append(root.data)
        self.dfs(root.left, depth+1, res)
        self.dfs(root.right, depth+1, res)
  

  使用 DFS, 用 level记录深度， root 深度为0。 (See problem 102)

Tricks

• Use recursive algorithm.
• Use DFS and BFS

Problems

Easy

• 098 Validate Binary Search Tree * (note)
• 101 Symmetric Tree * (note)
• 102 Binary Tree Level Order Traversal * (note)
• 104 Maximum Depth of Binary Tree * (note)
• 108 Convert Sorted Array to Binary Search Tree * (note)

Medium

• 094 Binary Tree Inorder Traversal * (note)
• 103 Binary Tree Zigzag Level Order Traversal * (note)
• 105 Construct Binary Tree from Preorder and Inorder Traversal * (note)
• 116 Populating Next Right Pointers in Each Node * (note)
• 200 Number of Islands * (note)
• 230 Kth Smallest Element in a BST * (note)
• 285 Inorder Successor in BST * (note)