Binary Tree

A Binary Tree is a hierarchical data structure in which every node has at most two children (left and right). The topmost node is called the root.

Terminology

• Root: The topmost node.
• Leaf: A node with no children.
• Parent: A node that has children.
• Child: A node that has a parent.
• Height: The length of the longest path of edges from the root to a leaf.
• Depth: The number of edges from the root to a given node.

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

# Building a binary tree
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

        1
       / \
      2   3
     / \
    4   5

Types of Binary Tree

Traversal

Inorder (Left, Root, Right)

def inorder(node):
    if not node:
        return []
    return inorder(node.left) + [node.val] + inorder(node.right)

print(inorder(root))  # [4, 2, 5, 1, 3]

Preorder (Root, Left, Right)

def preorder(node):
    if not node:
        return []
    return [node.val] + preorder(node.left) + preorder(node.right)

print(preorder(root))  # [1, 2, 4, 5, 3]

Postorder (Left, Right, Root)

def postorder(node):
    if not node:
        return []
    return postorder(node.left) + postorder(node.right) + [node.val]

print(postorder(root))  # [4, 5, 2, 3, 1]

Level-Order (BFS)

from collections import deque

def level_order(root):
    if not root:
        return []
    result = []
    queue = deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level)
    return result

print(level_order(root))  # [[1], [2, 3], [4, 5]]

Time Complexity

A Binary Tree becomes more powerful with a sorting property. Let's study the Binary Search Tree.