A binary tree is called full binary tree if each node has exactly two children and all leaf nodes are at the same level.

Applications of Binary Trees

Following are the some of the applications where binary trees play an important role:

• • Expression trees are used in compilers.
  • Huffman coding trees that are used in data compression algorithms.
  • Binary Search Tree (BST), which supports search, insertion and deletion on a collection of items in O(logn) (average).
  • Priority Queue (PQ), which supports search and deletion of minimum (or maximum)on a collection of items in logarithmic time (in worst case).
  • Binary Search Trees(BSTs) are used to quickly check whether an element is present in a set or not.
  • Heap is a kind of tree that is used for heap sort.
  • A modified version of a tree called Tries is used in modern routers to store routing information.
  • Most popular databases use B-Trees and T-Trees, which are variants of the tree structure we learned above to store their data
  • Compilers use a syntax tree to validate the syntax of every program you write.
  • In HTML, the Document Object Model (DOM) works as a tree.

@NoArgsConstructor
@AllArgsConstructor
@Data
@ToString
public class TreeNode {

    private User data;
    private TreeNode left;
    private TreeNode right;
    
    public TreeNode(User data) {
        this.data = data;
    }
}

@ToString
@NoArgsConstructor
@AllArgsConstructor
@Data
class User implements Serializable, Comparable<User> {

    /**
     * 
     */
    private static final long serialVersionUID = 1L;
    private String            name;
    private Integer           rating;

    @Override
    public int compareTo(User other) {
        // TODO Auto-generated method stub
        return this.rating.compareTo(other.getRating());
    }
}

Insert data into Binary Tree

public TreeNode insert(TreeNode parent, User data) {
    /**
     * if node is null, put the data there
     */
    if (parent == null) {
        return new TreeNode(data);
    }

    User parentData = parent.getData();

    /**
     * if parent is greater than new node, go left<br>
     * if parent is less than new node, go right<br>
     */
    if (parentData.getRating() > data.getRating()) {
        parent.setLeft(insert(parent.getLeft(), data));
    } else {
        parent.setRight(insert(parent.getRight(), data));
    }

    return parent;
}

public TreeNode insert(User data) {
    if(root==null) {
        root = new TreeNode(data);
        return root;
    }
    return insert(root,data);
}

public class BinaryTreeMain {

    public static void main(String[] args) {
        // TODO Auto-generated method stub

        TreeNode root = new TreeNode();

        root.setData(new User("Folau", 20));

        BinaryTree binaryTree = new BinaryTree(root);

        binaryTree.insert(new User("Lisa", 30));
        binaryTree.insert(new User("Laulau", 15));
        binaryTree.insert(new User("Kinga", 12));
        binaryTree.insert(new User("Fusi", 35));
        binaryTree.insert(new User("Nesi", 34));
        binaryTree.insert(new User("Melenesi", 32));
        

        System.out.println("PreOrder Traversal");
        
        binaryTree.preOrder(root, "root");
        
        System.out.println("InOrder Traversal");
        
        binaryTree.inOrder(root);
        
        System.out.println("PostOrder Traversal");
        
        binaryTree.postOrder(root);
    }

}

PreOrder Traversal
root - User(name=Folau, rating=20)
left - User(name=Laulau, rating=15)
left - User(name=Kinga, rating=12)
right - User(name=Lisa, rating=30)
right - User(name=Fusi, rating=35)
left - User(name=Nesi, rating=34)
left - User(name=Melenesi, rating=32)
InOrder Traversal
User(name=Kinga, rating=12)
User(name=Laulau, rating=15)
User(name=Folau, rating=20)
User(name=Lisa, rating=30)
User(name=Melenesi, rating=32)
User(name=Nesi, rating=34)
User(name=Fusi, rating=35)
PostOrder Traversal
User(name=Kinga, rating=12)
User(name=Laulau, rating=15)
User(name=Melenesi, rating=32)
User(name=Nesi, rating=34)
User(name=Fusi, rating=35)
User(name=Lisa, rating=30)
User(name=Folau, rating=20)

Now that inserting elements into binary tree is done. We have ways to navigate through or traverse a tree data structure.

We have two options. Breadth-First Search(BFS) and Depth-First Search(DFS)

Depth-First Search

DFS is an algorithm for traversing or searching tree data structure. One starts at the root and explores as far as possible along each branch before backtracking.

DFS explores a path all the way to a leaf before backtracking and exploring another path. There 3 types of DFS: pre-order, in-order, and post-order

Inorder traversal

1. First, visit all the nodes in the left subtree
2. Then the root node
3. Visit all the nodes in the right subtree

Time Complexity: O(n). Space Complexity: O(n)

/**
 * 1. Traverse the left subtree in Inorder.<br>
 * 2. Visit the root.<br>
 * 3. Traverse the right subtree in Inorder.<br>
 * Time Complexity: O(n). Space Complexity: O(n).<br>
 */
public void inOrder(TreeNode node) {
    if (node != null) {
        inOrder(node.getLeft());
        System.out.println(node.getData().toString());
        inOrder(node.getRight());
    }
}

Preorder traversal

1. Visit root node
2. Visit all the nodes in the left subtree
3. Visit all the nodes in the right subtree

Time Complexity: O(n). Space Complexity: O(n)

/**
 * 1. Visit the root.<br>
 * 2. Traverse the left subtree in Preorder.<br>
 * 3. Traverse the right subtree in Preorder.<br>
 * Time Complexity: O(n). Space Complexity: O(n).
 */
public void preOrder(TreeNode node) {
    if (node != null) {
        System.out.println(node.getData().toString());
        preOrder(node.getLeft());
        preOrder(node.getRight());
    }
}

Postorder traversal

1. Visit all the nodes in the left subtree
2. Visit all the nodes in the right subtree
3. Visit the root node

Time Complexity: O(n). Space Complexity: O(n).

/**
 * 1. Traverse the left subtree in Postorder.<br>
 * 2. Traverse the right subtree in Postorder.<br>
 * 3. Visit the root.<br>
 * Time Complexity: O(n). Space Complexity: O(n).<br>
 */
public void postOrder(TreeNode node) {
    if (node != null) {
        postOrder(node.getLeft());
        postOrder(node.getRight());
        System.out.println(node.getData().toString());
    }
}

Breadth-First Search

BFS is an algorithm for traversing or searching tree data structure. It starts at the tree root and explores the neighbor nodes first, before moving to the next level neighbors.

BFS algorithm traverses the tree level by level and depth by depth.

public void bfs() {

    int level = 1;
    queue.add(new LevelNode(root, level));

    while (queue.isEmpty() != true) {
        LevelNode levelNode = queue.poll();
        TreeNode node = levelNode.getNode();
        
        level++;
        
        // 1. process node
        System.out.println("level: "+levelNode.getLevel()+", data: "+ node.getData().toString());
        
        // 2. push left and right child nodes onto queue
        if(node.getLeft()!=null) {
            queue.add(new LevelNode(node.getLeft(), level));
        }
        
        if(node.getRight()!=null) {
            queue.add(new LevelNode(node.getRight(), level));
        }
        
    }
}

Source code on Github