Trees

Definition and Properties

A binary tree is a tree structure where each node has at most two direct descendants: the left child and the right child.

Recursive Definition

A binary tree is defined recursively as follows:

There is a special node called the root.
The remaining nodes are divided into two disjoint subtrees: left subtree and right subtree.

              R
             / \
           A1   A2

Binary Tree Properties

Each level i contains at most 2^i nodes.
A binary tree of height h has at most 2^(h+1) - 1 nodes.
The minimum height of a tree with n nodes is h ≥ log_2(n+1) - 1.

Special Types of Binary Trees

Strict Binary Tree

A strict binary tree is a tree where every node has exactly two children, except the leaves.

Full Binary Tree

A full binary tree is a strict binary tree where all terminal nodes are on the same level.

Complete Binary Tree

A complete binary tree has all levels filled except possibly the last, where nodes are as left-aligned as possible.

Binary Tree Representation

Parent Reference Representation

        k      1  2  3  4  5  6  7
        Parent 0  1  1  2  2  3  3
        Tip    0 -1  1 -1  1 -1  1

Child Reference Representation

        k     1  2  3  4  5  6  7
        Left  2  4  6  0  0  0  0
        Right 3  5  7  0  0  0  0

Binary Tree Implementation in Java

class Node {
    int data;
    Node left, right;

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

class BinaryTree {
    Node root;

    void preOrder(Node node) {
        if (node == null)
            return;
        System.out.print(node.data + " ");
        preOrder(node.left);
        preOrder(node.right);
    }
    
    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(5);
        tree.root.right.left = new Node(6);
        tree.root.right.right = new Node(7);
        
        System.out.println("Preorder Traversal:");
        tree.preOrder(tree.root);
    }
}

Tree Traversal Methods

Trees can be traversed in different ways:

Inorder (LNR): Left subtree → Root → Right subtree
Preorder (NLR): Root → Left subtree → Right subtree
Postorder (LRN): Left subtree → Right subtree → Root

        Inorder (LNR):  4 2 5 1 6 3 7
        Preorder (NLR): 1 2 4 5 3 6 7
        Postorder (LRN): 4 5 2 6 7 3 1

Binary Tree Representation Using Arrays

        int n, st[101], dr[101];
        
        void readTree() {
            Scanner sc = new Scanner(System.in);
            n = sc.nextInt();
            for (int i = 1; i <= n; i++) {
                st[i] = sc.nextInt();
            }
            for (int i = 1; i <= n; i++) {
                dr[i] = sc.nextInt();
            }
        }

Finding the Root

        int findRoot() {
            int[] v = new int[101];
            for (int i = 1; i <= n; i++) {
                if (st[i] != 0) v[st[i]] = -1;
                if (dr[i] != 0) v[dr[i]] = -1;
            }
            for (int i = 1; i <= n; i++) {
                if (v[i] == 0) return i;
            }
            return 0;
        }

Binary Tree Traversals

Inorder Traversal

        void inOrder(int x) {
            if (x != 0) {
                inOrder(st[x]);
                System.out.print(x + " ");
                inOrder(dr[x]);
            }
        }

Preorder Traversal

        void preOrder(int x) {
            if (x != 0) {
                System.out.print(x + " ");
                preOrder(st[x]);
                preOrder(dr[x]);
            }
        }

Postorder Traversal

        void postOrder(int x) {
            if (x != 0) {
                postOrder(st[x]);
                postOrder(dr[x]);
                System.out.print(x + " ");
            }
        }

Dynamic Binary Tree Representation

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

Creating the Tree

        void createTree(Node node, int x) {
            if (x == 0) return;
            node = new Node(x);
            System.out.print("Left child of " + x + " = ");
            Scanner sc = new Scanner(System.in);
            int leftChild = sc.nextInt();
            createTree(node.left, leftChild);
            
            System.out.print("Right child of " + x + " = ");
            int rightChild = sc.nextInt();
            createTree(node.right, rightChild);
        }

Deleting a Binary Tree

        void deleteTree(Node node) {
            if (node != null) {
                deleteTree(node.left);
                deleteTree(node.right);
                node = null;
            }
        }

Proper and Improper Ways to Delete a Subtree

Correct way:

        root.left = null;

Incorrect way:

        Node temp = root.left;
        temp = null;