↓Skip to main content

Binary Tree

·663 words·4 mins
Plaban Kumar Mondal
Author
Plaban Kumar Mondal
I am a cse student and a developer
Table of Contents

Introduction
#

A binary tree is a type of tree that can only have two children nodes at maximum. Example,

Binary Tree
Here 1 is the ‘root’ node. 2 and 3 are the children node of 1. Subsequently 4, 5 and 6 are the grandchildren of 1. Here we can see that node 2 is creating a tree structure of it’s own, it is a subtree of the main tree. 4, 5 and 6 are the leaf nodes who do not have any children nodes.

Types of Binary Trees
#

Full Binary Tree
#

Full binary trees either has 0 or 2 children.

Full Binary Tree

Complete Binary Tree
#

All the levels are completely filled except the last level. The last level has all nodes as left as possible.

Complete Binary Tree

Perfect Binary Tree
#

All the leaf nodes are at the same level.

Perfect Binary Tree

Balanced Binary Tree
#

The height of the tree can be at maximum of log(N). Where N is the number of nodes.

Following is the example of a balanced binary tree because the tree has 6 nodes, log2(8) = 3 and this tree has 3 levels.

Balanced Binary Tree
Following is the example of an unbalanced binary treebecause the tree has 8 nodes, log2(8) = 3 and this tree has 4 levels.
Unbalanced Binary Tree

Degenerate Tree
#

A degenerate tree is identical to linked list.

Degenerate Tree

Tree Representation in Java
#

class Node {
  int data;
  Node left;
  Node right;
  Node(int data) {
    this.data = data;
  }
}

// main function
public static void main(String[] args) {
  Node root = new Node(1);
  root.left = new Node(2);
  root.right = new Node(3);
  root.right.left = new Node(4);
}

Binary Tree Traversal
#

There is two main ways to traverse a binary tree.

  1. BFS (Breadth First Search)
  2. DFS (Depth First Search)

BFS Technique
#

It is a level wise traversing.

Binary Tree
BFS Traversal of this tree is 1, 2, 3, 4, 6, 7, 8, 9

DFS Technique
#

Inorder Traversal
#

In this traversal we use the logic of left -> root -> right. From the name In-order we can can see that root will be in the middle. First go to extreme left, then back to root, then right and follow the logic.

Binary Tree
Inorder: 4, 2, 5, 1, 6, 3, 7

Preorder Traversal
#

In this traversal we use the logic of root -> left -> right. From the name Pre-order we can can see that root will be at the front. First print root then all left then all right.

Binary Tree
Preorder: 1, 2, 4, 5, 3, 6, 7

Postorder Traversal
#

In this traversal we use the logic of left -> right -> root. From the name Post-order we can can see that root will be at the last. First print extreme left then right and finally root.

Binary Tree
Preorder: 4, 5, 2, 6, 7, 3, 1

Java Codes For The Traversals
#

Code for DFS techniques: preorder traversal, inorder traversal and postorder traversal.

// DFS
void preorder(Node node) {
  if(node == null)
    return;
  System.out.println(node.data);
  preorder(node.left);
  preorder(node.right);
}

void inorder(Node node) {
  if(node == null)
    return;
  inorder(node.left);
  System.out.println(node.data);
  inorder(node.right);
}

void postorder(Node node) {
  if(node == null)
    return;
  preorder(node.left);
  preorder(node.right);
  System.out.println(node.data);
}

Code for BFS technique.

public List<List<Integer>> levelOrder(TreeNode root) {
  List<List<Integer>> ans =  new ArrayList<>();
  Queue<TreeNode> q = new LinkedList<>();
  // check if the tree is empty or not
  if(root == null)
      return ans;
  // insert the root into the queue
  q.offer(root); // offer is same as add but checks if the queue is at max capacity or not
  // traverse through the queue
  while(!q.isEmpty()) {
      int levelSize = q.size();
      List<Integer> subList = new LinkedList<>();
      for(int i = 0; i < levelSize; i++) {
          // check if the current element in the queue has children
          // add the children in the queue
          if(q.peek().left != null)
              q.offer(q.peek().left);
          if(q.peek().right != null)
              q.offer(q.peek().right);
          // remove the current element and add to the sub list
          subList.add(q.poll().val); // we only need the int value
      }
      // finally add the sub list to the ans
      ans.add(subList);
  }
  return ans;
}