Binary Tree

Author: @wingkwong

Overview

A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child. The root node is the topmost node in the tree and the leaf nodes are the nodes at the bottom with no children. Binary trees are commonly used to implement data structures such as binary search trees, which are used for efficient searching and sorting. The height of the binary tree is the number of edges from the root to the deepest leaf node. The depth of a node is the number of edges from the root to that node.

Properties

• The number of nodes on level $l$ is equal to the $2^l$, like on level $0$ (root node) we got $2 ^ 0 >= 1$ node only.
• The Maximum number of nodes in a binary tree of height $h$ is $2^h - 1$.

Traversal

There are different ways to traverse trees - In-order, Pre-order, and Post-order. Supposing we have a binary tree with $5$ nodes,

Pre-order

• Visit the root
• Traverse the left sub-tree
• Traverse the right sub-tree

C++

void preorder(TreeNode* node) {
    if (node == NULL) return;
    s.push_back(node->val);
    preorder(node->left);
    preorder(node->right);
}

Python

def preorder(node):
    if (node == None): return
    s.append(node.val)    
    preorder(node.left)
    preorder(node.right)

In-order

• Traverse the left sub-tree
• Visit the root
• Traverse the right sub-tree

C++

void inorder(TreeNode* node) {
    if (node == NULL) return;
    inorder(node->left);
    s.push_back(node->val);
    inorder(node->right);
}

Python

def inorder(node):
    if (node == None): return
    inorder(node.left)
    s.append(node.val)
    inorder(node.right)

Post-order

• Traverse the left sub-tree
• Traverse the right sub-tree
• Visit the root

C++

void postorder(TreeNode* node) {
    if (node == NULL) return;
    postorder(node->left);
    postorder(node->right);
    s.push_back(node->val);
}

Python

def postorder(node):
    if (node == None): return
    postorder(node.left)
    postorder(node.right)
    s.append(node.val)  

Summary

Traversal	Path	Order
Pre-order	1 -> 2 -> 4 -> 5 -> 3	Root -> Left -> Right
In-order	4 -> 2 -> 5 -> 1 -> 3	Left -> Root -> Right
Post-order	4 -> 5 -> 2 -> 3 -> 1	Left -> Right -> Root