What is a Binary Tree?
A binary tree is a rooted tree (a tree is an undirected acyclic graph) in which each node has at most two child nodes (called left child and right child). A node having no child node is called a leaf node, and the remaining nodes are called internal nodes. The node at the top of the tree is called the root node. In this article, we will consider the level of root node r to be 0 and thus, the level of any node v would be the number of edges in the path from r to v.
Types of Binary Trees:
1. Full Binary Tree: It is a tree in which each node has either zero or two child nodes.
2. Complete Binary Tree: It is a tree in which all the levels are completely filled except possibly the last. And in the last level, all nodes are as much to the left as possible.
3. Perfect Binary Tree: In a perfect binary tree, all internal nodes have exactly two children and all the leaf nodes are at same level. Thus, all the levels are completely filled, including the last.
4. Balanced Binary Tree: It is a tree in which the difference between the heights of left and right subtrees of any node is at most 1.
Properties of Binary Trees:
- There is exactly one path from the root node r to any other node v in the tree.
- If number of nodes in a tree is n then number of edges in the tree is n-1.
- A tree does not have any cycles.
- In a perfect binary tree of height h, total number of nodes is n=2^(h+1)-1. Proof: At each level, number of nodes is 2ˡ, where l represents level. Thus, total number of nodes = 2⁰ + 2¹ + 2² + … + 2ʰ = 2^(h+1)-1 (using formula for Geometric Progression).
- Number of leaf nodes in a perfect binary tree is L=2ʰ. Therefore, number of internal nodes I = L-1, where L is the number of leaf nodes.
- If number of leaves in a full binary tree is L then number of internal nodes I = L-1, or we can say L = I+1. Proof: Assume we have a binary tree with three nodes — a root node with left and right children. For this tree, we can see that L = I + 1 holds true as we have 2 leaf nodes (children of root node) and 1 internal node (root node).
Now if we extend (or grow) this tree, we will have to add 2 nodes to any of the leaf node. We cannot extend this tree in any other way without violating the conditions of a full binary tree. So, if we add 2 child nodes to any of the leaf nodes then that leaf node will become an internal node. This will cause leaf nodes to decrease by 1 and number of internal nodes to increase by 1 — as the leaf node to which we attached 2 child nodes became an internal node. Thus, now number of leaf nodes is L-1 and number of internal nodes is I+1. However, we forgot to account for the 2 new leaf nodes that were added to the tree, so number of leaf nodes is actually L-1+2 = L+1. Thus, number of leaf nodes increased by 1 and number of internal nodes also increased by 1, maintaining the property L = I + 1 still holds true. Thus, whenever we grow this tree to hold more nodes, this property will still hold true. Thus, we proved this informally using induction.
Applications of Binary Tree (or n-ary tree):
- Folder structure in our operating system is modeled as an n-ary tree. Root folder being the root of the tree and then the directories and files inside it are its child nodes. These directories can again have any number of child nodes (files and more directories).
- The division of document structure into chapters, sections, etc. can also be modeled as an n-ary tree.
- Binary trees are used to implement Binary Search Trees and Binary Heaps which are used for efficient searching and sorting.
- Compression techniques like Huffman Coding also use Binary Tree for implementation.
- N-ary tree are used by compilers to create a syntax tree.
Different Type of Binary Tree traversals:
Before looking at different traversals methods, let’s first create a structure for tree nodes that we would be using in our code. As we can see below, tree is recursively defined structure, i.e., each node has references to nodes of the same type.
public class TreeNode {
public int value;
public TreeNode left;
public TreeNode right;
public TreeNode() {
}
public TreeNode(int value, TreeNode left, TreeNode right) {
this.value = value;
this.left = left;
this.right = right;
}
public TreeNode(int value) {
this.value = value;
}
}Depth First Traversal (or Depth First Search (DFS)):
In this kind of traversal, we completely visit (or process or access) deeper levels of a tree first before completely processing shallower levels. To accomplish this, we move further along one child node of a particular node before processing other nodes at the same level.
Recursion is a natural method to do depth-first traversals given that tree is a recursive data structure.
Three basic kinds of depth-first traversals are described below:
1. Preorder Traversal:
Pseudocode:
i. process the current node
ii. do preorder traversal for the left subtree
iii. do preorder traversal for the right subtree
This kind of traversal can give a topologically sorted order (if there is a dependancy) of nodes, as each parent node is process before its child nodes.
Recursive Code:
public void preorderTraversal(TreeNode root) {
if(root != null) {
process(root.value);
preorderTraversal(root.left);
preorderTraversal(root.right);
}
}Complexity: As each node is processed exactly once, the complexity is O(n) where n is the number of nodes in the tree.
Iterative code using Stack:
public void iterativePreorderTraversal(TreeNode root) {
if(root == null) {
return;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode node;
stack.push(root);
while(!stack.empty()) {
node = stack.pop();
process(node);
if(node.right != null) {
stack.push(node.right);
}
if(node.left != null) {
stack.push(node.left);
}
}
}Complexity: As each node is pushed into and popped out of the stack only once, the complexity is O(n) where n is the number of nodes in the tree.
Another iterative approach using Stack:
public void iterativePreorderTraversal(TreeNode root) {
if(root == null) {
return;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode node = root;
while(!stack.empty() || node != null) {
if(node != null) {
process(node);
stack.push(node);
}
else {
node = stack.pop().right;
continue;
}
node = node.left;
}
}2. Inorder Traversal:
Pseudocode:
i. do inorder traversal for the left subtree
ii. process the current node
iii. do inorder traversal for the right subtree
Inorder traversal can give a sorted order of nodes in a binary search tree (a tree in which each node is greater than all of the nodes in its left subtree and less than all of the nodes in its right subtree).
Recursive Code:
public void inorderTraversal(TreeNode root) {
if(root != null) {
inorderTraversal(root.left);
process(root);
inorderTraversal(root.right);
}
}Complexity: As each node is processed exactly once, the complexity is O(n) where n is the number of nodes in the tree.
Iterative code using Stack:
public void iterativeInorderTraversal(TreeNode root) {
if(root == null) {
return;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode node = root;
while(!stack.empty() || node != null) {
if (node != null) {
stack.push(node);
node = node.left;
}
else {
node = stack.pop();
process(node);
node = node.right;
}
}
}Complexity: As each node is pushed into and popped out of the stack only once, the complexity is O(n) where n is the number of nodes in the tree.
3. Postorder Traversal:
Pseudocode:
i. do postorder traversal for the left subtree
ii. do postorder traversal for the right subtree
iii. process the current node
Postorder traversal can be used while de-allocating the memory taken up by the tree. This will ensure that memory of child nodes is freed before freeing up their parent node.
Recursive Code:
public static void postorderTraversal(TreeNode root) {
if(root != null) {
postorderTraversal(root.left);
postorderTraversal(root.right);
process(root);
}
}Complexity: As each node is processed exactly once, the complexity is O(n) where n is the number of nodes in the tree.
Iterative code using two Stacks:
public void iterativePostorderTraversal(TreeNode root) {
if(root == null) {
return;
}
Stack<TreeNode> mainStack = new Stack<>();
Stack<TreeNode> unprocessedNodeStack = new Stack<>();
TreeNode node = root;
while(!mainStack.empty() || node != null) {
if(node != null) {
if(node.right != null) {
unprocessedNodeStack.push(node.right);
}
mainStack.push(node);
node = node.left;
}
else {
node = mainStack.peek();
if(!unprocessedNodeStack.isEmpty() && node.right == unprocessedNodeStack.peek()) {
node = unprocessedNodeStack.pop();
} else {
process(node);
mainStack.pop();
node = null;
}
}
}
}Complexity: As each node is pushed into and popped out of the mainStack only once, and each node is pushed into the unprocessedNodeStack at most once, the complexity is O(n) where n is the number of nodes in the tree.
Another iterative approach using a stack and a set:
public void iterativePostorderTraversalUsingSet(TreeNode root) {
if(root == null) {
return;
}
Stack<TreeNode> stack = new Stack<>();
Set<TreeNode> visitedNodeSet = new HashSet<>();
TreeNode node = root;
while(!stack.empty() || node != null) {
if(node != null) {
if(visitedNodeSet.contains(node)) {
process(node);
node = null;
} else {
stack.push(node);
if(node.right != null) {
stack.push(node.right);
}
visitedNodeSet.add(node);
node = node.left;
}
}
else {
node = stack.pop();
}
}
}Complexity: As each node is pushed into and popped out of the stack only once, and also each node is added to the set only once, the complexity is O(n) where n is the number of nodes in the tree.
Breadth First Traversal (BFS):
In BFS or level order traversal, we visit all the nodes of a level before visiting nodes of the next level.
This kind of traversal can be used when searching the tree for a particular node. If the target node is the rightmost node at the first level then DFS would take a lot more to find the target node than BFS.
Pseudocode:
i. create a queue, and push root node into this queue
ii. while the queue is not empty, loop over steps iii to iv
iii. remove the first node from the queue, process it
iv. push all its child nodes into the queue
Iterative code using queue:
public void bfs(TreeNode root) {
TreeNode node;
Queue<TreeNode> queue = new ArrayDeque<>();
queue.add(root);
while(!queue.isEmpty()) {
node = queue.remove();
process(node);
if(node.left != null) {
queue.add(node.left);
}
if(node.right != null) {
queue.add(node.right);
}
}
}Complexity: As each node is pushed into and removed from the queue only once, the complexity is O(n) where n is the number of nodes in the tree.
