Chapter 27 :Binary Tress(Part 1)

In this chapter, we dive deep into one of the most fundamental and essential data structures in computer science: Binary Trees (BT). Binary Trees are hierarchical structures that play a significant role in numerous algorithms and applications, including searching, sorting, and traversing data. This chapter serves as an introduction to Binary Trees and their associated operations, focusing on various traversal techniques, calculating tree height, counting nodes, finding sums, and determining the tree's diameter using different approaches. Let's start with an overview of what a Binary Tree is and how it forms the foundation of many advanced data structures like Binary Search Trees (BSTs), Heaps, and more.

---

1. Introduction to Binary Trees

We are specifically learning about Binary Trees (BT) because they are crucial for interview preparation and are widely used in technical problem-solving. A tree is a hierarchical data structure (DS) that resembles a family tree, where elements are organized level by level. This structure, known as hierarchical, is perfect for storing data that has a natural hierarchy. For instance, if we want to store information with a structured format in code, we use tree data structures.

If we imagine a tree in real life with roots, branches, and leaves, a binary tree mirrors this structure in code. However, there's a slight change: we swap the concept of root and leaves. The root is the topmost node, and the leaves are the nodes without further branches.

A Binary Tree is a special type of tree where each node can have at most two children. These children are referred to as the left child and the right child. The topmost node is called the root, and nodes without children are called leaf nodes. Binary Trees are integral to various applications, such as:

• Expression parsing (used in calculators and compilers),

• Syntax tree representation in compilers,

• Database indexing for quick retrieval of data.

Binary Trees are essential for efficiently searching, organizing, and manipulating data. They can be classified into several types:

• Full Binary Tree: Each node has either 0 or 2 children. No node has only one child.

• Complete Binary Tree: All levels are fully filled except possibly the last, and all nodes in the last level are as far left as possible.

• Perfect Binary Tree: All internal nodes have exactly two children, and all leaf nodes are at the same level.

These classifications highlight the different ways binary trees can be structured, each with its use cases and advantages. While we will explore these variations in detail in future chapters, our current focus will be on understanding the basic operations of binary trees, such as building them, traversing them, and calculating their properties.

2. Levels and Sub-trees in a Tree

Levels

In a binary tree, the level of a node represents its position in the hierarchy. It starts from the root node, which is at level 1, and increases as we move down the tree. Each subsequent level contains the children of the nodes from the previous level. Here's a breakdown:

• The node at the topmost position is the root and is at Level 1.

• The next set of nodes (children of the root) are at Level 2.

• The children of the nodes in Level 2 form Level 3, and so on.

Example:

• Node 1 is at Level 1.

• Nodes 2 and 3 are at Level 2.

• Nodes 4, 5, and 6 are at Level 3.

• Nodes 7, 8, and 9 are at Level 4.

Depth

The depth of a node is the distance from the root node to that particular node. It’s essentially the level number of the node, as the depth starts counting from the root:

• The depth of nodes in Level 1 is 1.

• The depth of nodes in Level 2 is 2.

• The depth of nodes in Level 3 is 3, and so on.

Example:

• The depth of Node 7 (which is in Level 4) is 4.

Subtree

A subtree is a portion of the tree that consists of a node and all of its descendants. In other words, every node in a binary tree can be considered the root of its own subtree.

Example:

• The subtree rooted at Node 2 has:

  • Left subtree containing Nodes 4, 7, and 8.

  • Right subtree containing Node 5.

Each node has its own subtree, including all the nodes branching off from it. Subtrees are a fundamental concept when manipulating and traversing trees, as they allow us to break down problems into smaller, more manageable parts.

3. Pop Quiz

Test your understanding of binary trees with the following questions:

A. Children of 4:

• The children of Node 4 are 7 and 8.

B. Number of leaves:

• The leaf nodes are 7, 8, 9, and 5. So, there are 4 leaf nodes in total.

C. Parent of 6:

• The parent of Node 6 is Node 3.

D. Level of 2:

• Node 2 is at Level 2.

E. Subtrees of 1 and 2:

• For Node 1:

  • Left Subtree: Includes Nodes (2, 4, 5, 7, 8).

  • Right Subtree: Includes Nodes (3, 6, 9).

• For Node 2:

  • Left Subtree: Includes Nodes (4, 7, 8).

  • Right Subtree: Node 5.

F. Ancestors of 8:

• The ancestors of Node 8 are 4, 2, and 1.

---

4. Building a Binary Tree (Preorder)

To understand binary trees better, let's build one using preorder traversal. In preorder traversal, nodes are visited in the following sequence:

1. Visit the root.

2. Traverse the left sub-tree.

3. Traverse the right sub-tree.

This recursive pattern is vital for creating and navigating binary trees. Here's how we can build a binary tree using this approach:

class Node {
    int data;
    Node left, right;

    Node(int value) {
        data = value;
        left = right = null;
    }
}

public class BinaryTree {
    static int index = -1;

    public static Node buildTree(int[] nodes) {
        index++;
        if (index >= nodes.length || nodes[index] == -1) {
            return null;
        }

        Node newNode = new Node(nodes[index]);
        newNode.left = buildTree(nodes);
        newNode.right = buildTree(nodes);

        return newNode;
    }
}

5. Preorder Traversal

Preorder Traversal follows the same order as above (root, left, right). It’s useful for copying tree structures or evaluating prefix expressions. Here's the code for preorder traversal:

public static void preorder(Node root) {
    if (root == null) return;
    System.out.print(root.data + " ");
    preorder(root.left);
    preorder(root.right);
}

6. Inorder Traversal

In Inorder Traversal, the sequence is:

1. Traverse the left sub-tree.

2. Visit the root.

3. Traverse the right sub-tree.

Inorder traversal is especially useful for retrieving nodes in non-decreasing order for a BST:

public static void inorder(Node root) {
    if (root == null) return;
    inorder(root.left);
    System.out.print(root.data + " ");
    inorder(root.right);
}

7. Postorder Traversal

Postorder Traversal sequence:

1. Traverse the left sub-tree.

2. Traverse the right sub-tree.

3. Visit the root.

Postorder traversal is essential for deleting nodes or evaluating postfix expressions:

public static void postorder(Node root) {
    if (root == null) return;
    postorder(root.left);
    postorder(root.right);
    System.out.print(root.data + " ");
}

8. Level Order Traversal

In Level Order Traversal, nodes are visited level by level, from top to bottom. This traversal uses a queue data structure:

public static void levelOrder(Node root) {
    if (root == null) return;
    Queue<Node> queue = new LinkedList<>();
    queue.add(root);

    while (!queue.isEmpty()) {
        Node current = queue.poll();
        System.out.print(current.data + " ");
        if (current.left != null) queue.add(current.left);
        if (current.right != null) queue.add(current.right);
    }
}

9. Height of a Tree

The height of a tree is the longest path from the root to any leaf node. We can calculate it recursively:

public static int height(Node root) {
    if (root == null) return 0;
    int leftHeight = height(root.left);
    int rightHeight = height(root.right);
    return Math.max(leftHeight, rightHeight) + 1;
}

10. Count Nodes of a Tree

Counting the total number of nodes in a tree:

public static int countNodes(Node root) {
    if (root == null) return 0;
    return countNodes(root.left) + countNodes(root.right) + 1;
}

11. Sum of Nodes

Calculating the sum of all nodes in the tree:

public static int sumOfNodes(Node root) {
    if (root == null) return 0;
    return sumOfNodes(root.left) + sumOfNodes(root.right) + root.data;
}

12. Diameter of a Tree (Approach 1)

The diameter of a tree is the longest path between any two nodes. Approach 1 uses recursion to calculate it:

public static int diameter(Node root) {
    if (root == null) return 0;
    int leftHeight = height(root.left);
    int rightHeight = height(root.right);
    int leftDiameter = diameter(root.left);
    int rightDiameter = diameter(root.right);

    return Math.max(leftHeight + rightHeight + 1, Math.max(leftDiameter, rightDiameter));
}

13. Diameter of a Tree (Approach 2)

Approach 2 optimizes the calculation by using a pair (height and diameter):

class TreeInfo {
    int height, diameter;
    TreeInfo(int height, int diameter) {
        this.height = height;
        this.diameter = diameter;
    }
}

public static TreeInfo diameterOptimized(Node root) {
    if (root == null) return new TreeInfo(0, 0);
    TreeInfo left = diameterOptimized(root.left);
    TreeInfo right = diameterOptimized(root.right);

    int myHeight = Math.max(left.height, right.height) + 1;
    int myDiameter = Math.max(left.height + right.height + 1, Math.max(left.diameter, right.diameter));

    return new TreeInfo(myHeight, myDiameter);
}

---

Conclusion

In this chapter, we explored the basics of Binary Trees, different traversal techniques, and operations like calculating the height, counting nodes, finding the sum, and computing the diameter using two approaches. Understanding these fundamental operations is crucial as we build more complex structures in future chapters.

Hope you enjoyed learning! Stay tuned for Part 2, where we explore more advanced topics in Binary Trees!

Related Posts in My Series:

DSA in Java Series:

• Chapter 2: Operators in Java – Learn about the different types of operators in Java, including arithmetic, relational, logical, and assignment operators, along with examples to understand their usage.

• Chapter 33: Trie in Java – Explore the implementation and use of Trie data structure in Java, a powerful tool for handling strings, with practical coding examples.

Other Series:

• Full Stack Java Development – Master the essentials of Java programming and web development with this series. Topics include object-oriented programming, design patterns, database interaction, and more.

• Full Stack JavaScript Development – Become proficient in JavaScript with this series covering everything from front-end to back-end development, including frameworks like React and Node.js.

---

Connect with Me
Stay updated with my latest posts and projects by following me on social media:

• LinkedIn: Connect with me for professional updates and insights.

• GitHub: Explore my repositories and contributions to various projects.

• LeetCode: Check out my coding practice and challenges.

Your feedback and engagement are invaluable. Feel free to reach out with questions, comments, or suggestions. Happy coding!

Rohit Gawande
Full Stack Java Developer | Blogger | Coding Enthusiast