Binary Trees

07 Oct 2017 View Comments #binary #tree #traversal #programming Binary tree” is the tree in which every node has at most 2 children, which are referred to as the left child and the right child. Trees can certainly have multiple leaves (n-ary, b-tree), trie structure, heap structure and much more. Binary Tree is one of the simple and popular tree structure out of many kinds of trees. It really is basically a 2-ary tree. The tree is often interchangeable with the undirected graph. In a binary tree, it is a graph with at most 2 edges stemming out of a to create at most 2 vertices at t. The topmost node in the tree is called the root. This is the vertice that starts the whole tree. Therefore typically, we refer to a binary tree as a directed graph since it begins from top to bottom in most of the case.

Types of Binary Tree

Full (Strict) Binary Tree

A binary tree T with n levels is “full” if the tree nodes have 0 or 2 children. Following are examples of full binary tree

Complete Tree

A binary tree T with n levels is “complete” if all levels except possibly the last are completely full

Full And Complete Tree

In a full binary tree,

• # of min nodes are $n = h + 1 (root)$
• # of max nodes are $n = 2^{(h+1)} - 1$

In a perfect binary tree (full and complete binary tree),

• # of min nodes are $n = 2^{h}$
• # of max nodes are $n = 2^{(h+1)} - 1$

Balanced Binary Tree

Before we define what balanced binary tree is, we should examine what height/depth of a tree is. The height of a node is the number of edges from the node to the deepest leaf. Now that we have the height in mind, what is a balanced tree? A rooted binary tree of height “h” is balanced if all leaves are perfect at levels h “or” h − 1. It is important to say that all complete trees are balanced trees, all balanced trees are not necessarily complete trees. See the example below:

Above is a balanced binary tree but not a complete binary tree.

Here is an example code (in Java) which checks whether given tree is balanced:

Note there is a function for calculating the height because it needs to know that to understand the tree is balanced. Basically the function recurses all the way down to the tree by validating the height difference (cannot be greater than 1)until the base case is hit (root == null).

Binary Search Tree (BST)

We saw what it means to be a tree to be balanced. Here is another form of a binary tree that allows for a faster search. It produces O(log n) when a tree is balanced. When a tree with n nodes is kept balanced, its height is always O(log n). This is why we have self-balancing (height-balanced) binary search trees such as AVL (1962), 2-3 Tree (1970) or Red-Black Tree (1972). These trees would make additional effort in insertion/removal of the nodes to keep the tree balanced by rotating trees around in an efficient way to keep the complexity at O(log n). Without balancing the trees, the tree could be skewed to one side. In extreme cases, it would basically be a O(n) searching.

Check checkBST function to see how it validates BST:

Above code would recurse left tree first and check whether all nodes are in BST mode. Then check the right by doing the same check. When every nodes are validated, the function returns “PASS”.

Here is a bit more simpler way of check using recursion:

Above code recurses left and right subtrees and check if the value is set properly to BST rule. Returns false if the tree violates the BST rule.

Tree Traversal

The idea of traversal on the tree really stemmed from graph traversal and applied to the tree which refers to the similar process of visiting each node. Since the traversal requires visiting all the nodes, the time complexity of this operation is usually O(n) either a tree or a graph. The difference between the traversal on graph vs tree would be an indication of whether the node is visited or not in a vertices because unlike the binary trees (top-down approach), graphs could have multiple branches/edges and can quickly recurse on the same traversal which could end up with infinite recursion unless we mark it properly as a “visited” node.

Depth-First Search (DFS)

Trees can be traversed using a Depth First Search algorithm. There are 3 different methods for traversing the tree and they all start from the root node.

Pre-order

Purpose of this traversal is to visit the root node before proceeding to each child nodes. Used for copying/cloning the tree.

Performed in this order recursively:

1. Check if the current node is empty / null.
2. Display the data part of the root (or current node).
3. Traverse the left subtree by recursively calling the pre-order function.
4. Traverse the right subtree by recursively calling the pre-order function.

Here is an example code:

In-order

This traversal is very useful in search trees, as it will retrieve and flatten the nodes in sorted order.

Performed in this order recursively:

1. Check if the current node is empty/null.
2. Traverse the left subtree by recursively calling the in-order function.
3. Display the data part of the root (or current node).
4. Traverse the right subtree by recursively calling the in-order function.

Here is an example code:

Post-order

If you know you need to explore all the leaves first starting from the left side, use this traversal. This traversal is useful in an expression tree that is to do with calculating stuff.

Performed in this order recursively:

1. Check if the current node is empty/null.
2. Traverse the left subtree by recursively calling the post-order function.
3. Traverse the right subtree by recursively calling the post-order function.
4. Display the data part of the root (or current node).

Here is an example code: 