Introduction to Binary Tree

General Ideas

graph TD;
    	1 -->2;
    	1-->3;
	2-->4;
	2-->5;
	3-->6;
	3-->7;

There are some terminologies we need to know:

• Node: Each element in the tree is called a node.
• Root: The top node of the tree.
• Parent: A node that has children nodes.
• Child: A node that has a parent node.
• Leaf: A node that does not have any children nodes.
• Subtree: A tree that is a part of a larger tree.
• Height: The number of edges on the longest path from the root to a leaf

Lets take a example below:

graph TD;
    	1 -->2;
    	1-->3;
    2-->4;
    2-->5;
    3-->6;
    3-->7;
    4-->8;
    4-->9;
    5-->10;
    5-->11;
    6-->12;
    6-->13;
    7-->14;
    7-->15;

• The root is 1
• The parent of 2 is 1
• The children of 2 are 4 and 5
• The leaves are 8, 9, 10, 11, 12,
• The subtree rooted at 2 is:

graph TD;
    2-->4;
    2-->5;
    4-->8;
    4-->9;
    5-->10;
    5-->11;

different types of binary trees

• Full Binary Tree: A binary tree in which every node has either 0 or 2 children. (No node has only one child)
• Perfect Binary Tree: A binary tree in which all internal nodes have two children and all leaves are at the same level.
• Complete Binary Tree: A binary tree in which all levels are completely filled except possibly the last level, which is filled from left to right.
• Balanced Binary Tree: A binary tree in which the height of the two subtrees of any node never differs by more than one.
• Binary Search Tree (BST): A binary tree in which for each node, the left subtree contains only nodes with values less than the node’s value, and the right subtree contains only nodes with values greater than the node’s value.

Implementation

class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

Notes:

• If you think about it, it feels like a variant of doubly linked list.
• HashMap can also be implemented using binary tree.

Traversal

To traverse a data structure means to visit all the nodes in a specific order.

There are three different timing we can traverse

• Preorder traverse
• Inorder traverse
• Postorder traverse

Example of DFS traversal:

DFS stands for Depth First Search. It explores as far as possible along each branch before backtracking.

void traverse(TreeNode* root){
    if(root == NULL) return;
    // Preorder: visit root first
    traverse(root->left);
    // Inorder: visit left subtree first
    traverse(root->right);
    // Postorder: visit right subtree first
}

The order of visiting the nodes are fixed.

Example of BFS:

BFS stands for Breadth First Search. It explores all the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level.

A queue has FIFO(First In First Out) property, which is used in BFS.

There are three implementations:

• No node depth info
• Node depth info
• customizable depth info

Multiway Tree

multiway tree is an extension of a binary tree where each node can have more than two children. binary tree is a special case of multiway tree where each node has at most two children. forest is a collection of disjoint multiway trees.

class MultiwayTreeNode {
public:
    int val;
    vector<MultiwayTreeNode*> children; // A list of child nodes
    MultiwayTreeNode(int x) : val(x) {}
};

DFS Traversal of Multiway Tree

void travese(MultiwayTreeNode* root) {
    if (root == NULL) return;
  
    // Preorder: visit root first
    for (MultiwayTreeNode* child : root->children) {
        travese(child);
    }
    // Postorder: visit children first
}

We use DFS to find all the paths from root to leaf nodes. We use BFS to find the shortest path from root to a target node.

Binary Search Tree (BST)

BST when doing inorder traversal, the nodes are visited in ascending order.