Binary Tree

A Tree is a hierarchical data structure consisting of nodes. A Binary Tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child.

Tree Terminology

• Root: The topmost node of the tree.
• Parent: Every node (excluding the root) is directed by a node called a parent.
• Child: A node directly connected to another node when moving away from the root.
• Leaf: A node with no children.

Visual Representation

Traversals

Traversing a tree means visiting every node in the tree. Because it is non-linear, there isn't just one logical order.

1. Inorder (Left, Root, Right): 3 -> 5 -> 7 -> 10 -> 12 -> 15 -> 18
2. Preorder (Root, Left, Right): 10 -> 5 -> 3 -> 7 -> 15 -> 12 -> 18
3. Postorder (Left, Right, Root): 3 -> 7 -> 5 -> 12 -> 18 -> 15 -> 10

Java Implementation

public class BinaryTree {

    class Node {
        int key;
        Node left, right;

        public Node(int item) {
            key = item;
            left = right = null;
        }
    }

    Node root;

    public void inorder(Node node) {
        if (node == null)
            return;
        inorder(node.left);
        System.out.print(node.key + " ");
        inorder(node.right);
    }
    
    public void preorder(Node node) {
        if (node == null)
            return;
        System.out.print(node.key + " ");
        preorder(node.left);
        preorder(node.right);
    }
    
    public void postorder(Node node) {
        if (node == null)
            return;
        postorder(node.left);
        postorder(node.right);
        System.out.print(node.key + " ");
    }

    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();
        tree.root = tree.new Node(10);
        tree.root.left = tree.new Node(5);
        tree.root.right = tree.new Node(15);
        
        System.out.println("Inorder traversal:");
        tree.inorder(tree.root);
    }
}