Height of Binary Tree in DSA Java - Build from Scratch

Height of Binary Tree

📖 Scenario: You are working on a program that helps analyze family trees. Each person is represented as a node in a binary tree, where each node can have up to two children (left and right). You want to find out how tall the family tree is, which means finding the longest path from the root person down to the farthest descendant.

🎯 Goal: Build a Java program that creates a simple binary tree, sets up a helper method to calculate the height of the tree, and then prints the height.

📋 What You'll Learn

Create a binary tree with exactly 5 nodes with these values: 1, 2, 3, 4, 5

Add a helper method called height that calculates the height of the binary tree

Use recursion in the height method to find the height

Print the height of the binary tree

💡 Why This Matters

🌍 Real World

Binary trees are used in many applications like family trees, decision trees, and organizing data for quick search.

💼 Career

Understanding tree structures and recursion is important for software development roles involving data processing, algorithms, and system design.

1

Create the Binary Tree Nodes

Create a class called Node with an integer data field and two Node fields called left and right. Then create a binary tree with root node root having value 1. Add left child with value 2 and right child with value 3. Add left child of node 2 with value 4 and right child of node 2 with value 5.

DSA Java

class Node {
    int data;
    Node left, right;

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

public class BinaryTree {
    public static void main(String[] args) {
        // Your code here
    }
}

Hint

Define the Node class with data, left, and right. Then create the root and its children exactly as described.

2

Add the Height Method Signature

Inside the BinaryTree class, add a static method called height that takes a Node parameter called node and returns an int. This method will calculate the height of the binary tree starting from the given node.

DSA Java

class Node {
    int data;
    Node left, right;

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

public class BinaryTree {
    public static int height(Node node) {
        // Your code here
    }

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

Hint

Write the height method with a base case for null nodes returning 0. Then recursively find the height of left and right children and return the larger one plus 1.

3

Calculate the Height of the Tree

In the main method, call the height method with the root node and store the result in an integer variable called treeHeight.

DSA Java

class Node {
    int data;
    Node left, right;

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

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

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

        // Your code here
    }
}

Hint

Call height(root) and save the result in treeHeight.

4

Print the Height of the Tree

Add a System.out.println statement in the main method to print the text "Height of the tree: " followed by the value of treeHeight.

DSA Java

class Node {
    int data;
    Node left, right;

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

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

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

        int treeHeight = height(root);
        // Your code here
    }
}

Hint

Use System.out.println("Height of the tree: " + treeHeight); to print the height.

Practice

1. What is the height of a binary tree with only one node (the root)?

easy

A. Undefined

B. 1

C. 2

D. 0

Solution

1. Step 1: Understand height definition

   The height of a binary tree is the number of edges on the longest path from the root to a leaf.

2. Step 2: Apply to single node tree

   With only one node (root), the longest path has length 0 edges.

3. Final Answer:

   0 -> Option D

4. Quick Check:

   Single node tree height = 0 [OK]

Hint: Height counts edges on longest root-to-leaf path [OK]

Common Mistakes:

• Thinking height is 1 for single node
• Confusing height with number of nodes
• Assuming height undefined for single node

2. Which of the following Java method signatures correctly defines a recursive method to find the height of a binary tree node?

easy

A. public int height(Node root)

B. int height(Node root) void

C. public void height(Node root) returns int

D. height(Node root) int public

Solution

1. Step 1: Check Java method syntax

   Java methods must specify access modifier, return type, method name, and parameters correctly.

2. Step 2: Validate each option

   public int height(Node root) follows correct syntax: public int height(Node root). Others have syntax errors.

3. Final Answer:

   public int height(Node root) -> Option A

4. Quick Check:

   Correct Java method signature = public int height(Node root) [OK]

Hint: Java method: access + return type + name + parameters [OK]

Common Mistakes:

• Wrong order of return type and name
• Missing return type
• Using void with return value

3. What will be the output of the following Java code snippet?

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

public class Test {
  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;
  }

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

medium

A. 1

B. 3

C. 2

D. 4

Solution

1. Step 1: Visualize the tree structure

   The tree has root 1, left child 2, right child 3, and left child of 2 is 4. The longest path is 1->2->4.

2. Step 2: Calculate height recursively

   Height is max depth: left subtree height = 2 (nodes 2->4), right subtree height = 1 (node 3), so total height = max(2,1)+1 = 3.

3. Final Answer:

   3 -> Option B

4. Quick Check:

   Longest path length = 3 [OK]

Hint: Height = longest root-to-leaf path node count [OK]

Common Mistakes:

• Counting edges instead of nodes
• Ignoring null child base case
• Misreading tree structure

4. Identify the error in the following Java method to find the height of a binary tree:

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

medium

A. The method should not use recursion.

B. The method should return the sum of left and right heights.

C. The base case should return 0, not -1.

D. The method should return the minimum of left and right heights.

Solution

1. Step 1: Check base case return value

   Height of empty tree (null) should be 0 or consistent with counting edges. Returning -1 causes incorrect height calculation.

2. Step 2: Check return statement

   Method returns max of left and right heights but misses adding 1 for current node, so height is underestimated.

3. Final Answer:

   The base case should return 0, not -1. -> Option C

4. Quick Check:

   Base case must return 0 for correct height [OK]

Hint: Base case return 0, add 1 after max height [OK]

Common Mistakes:

• Returning -1 in base case
• Not adding 1 to max height
• Returning sum instead of max

5. Given a binary tree where each node stores an integer, write a method to find the height of the tree and then print all nodes at the maximum height level. Which approach correctly combines these tasks?

hard

A. First find height recursively, then use a level-order traversal to print nodes at that height.

B. Print nodes during height calculation without storing height separately.

C. Use in-order traversal to print nodes at maximum height level directly.

D. Calculate height by counting nodes and print nodes at root only.

Solution

1. Step 1: Find height recursively

   Use a recursive method to find the height of the tree, which gives the maximum depth level.

2. Step 2: Use level-order traversal

   Perform a breadth-first traversal (level-order) and print nodes only at the level equal to the height found.

3. Final Answer:

   First find height recursively, then use a level-order traversal to print nodes at that height. -> Option A

4. Quick Check:

   Separate height calculation + level-order print = First find height recursively, then use a level-order traversal to print nodes at that height. [OK]

Hint: Find height first, then print nodes at that level [OK]

Common Mistakes:

• Trying to print during height recursion
• Using in-order traversal for level nodes
• Printing root only ignoring height