Tree Terminology Root Leaf Height Depth Level in DSA Java - Build from Scratch

Tree Terminology: Root, Leaf, Height, Depth, Level

📋 What You'll Learn

💡 Why This Matters

🌍 Real World

Trees are used to represent hierarchical data like family trees, file systems, and organizational charts.

💼 Career

Understanding tree terminology and traversal is essential for software development roles involving data structures, databases, and UI component trees.

1

Create the Tree Nodes and Root

Create a class called TreeNode with a String name and a list of children called children. Then create a TreeNode variable called root with the name "Grandparent" and no children yet.

DSA Java

class TreeNode {
    String name;
    List children;

    TreeNode(String name) {
        this.name = name;
        this.children = new ArrayList();
    }
}

// Your code here

Hint

Define the TreeNode class with a constructor. Then create the root node with name "Grandparent".

2

Add Children to the Tree

Create two TreeNode variables called parent1 and parent2 with names "Parent1" and "Parent2". Add them as children to the root. Then create two children for parent1 called child1 and child2 with names "Child1" and "Child2", and add them as children to parent1. Leave parent2 without children.

DSA Java

import java.util.ArrayList;
import java.util.List;

class TreeNode {
    String name;
    List children;

    TreeNode(String name) {
        this.name = name;
        this.children = new ArrayList();
    }
}

public class TreeTerminology {
    public static void main(String[] args) {
        TreeNode root = new TreeNode("Grandparent");
        // Your code here
    }
}

Hint

Create the parent and child nodes and add them to the correct parent's children list.

3

Calculate Height, Depth, and Identify Leaves

Write a method called height that takes a TreeNode and returns the height of the tree from that node. Write a method called depth that takes a TreeNode, the root, and returns the depth of that node. Write a method called isLeaf that returns true if the node has no children. Use recursion for height and depth calculations.

DSA Java

import java.util.ArrayList;
import java.util.List;

class TreeNode {
    String name;
    List children;

    TreeNode(String name) {
        this.name = name;
        this.children = new ArrayList();
    }
}

public class TreeTerminology {
    public static int height(TreeNode node) {
        // Your code here
    }

    public static int depth(TreeNode node, TreeNode root) {
        // Your code here
    }

    public static boolean isLeaf(TreeNode node) {
        // Your code here
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode("Grandparent");
        TreeNode parent1 = new TreeNode("Parent1");
        TreeNode parent2 = new TreeNode("Parent2");
        root.children.add(parent1);
        root.children.add(parent2);

        TreeNode child1 = new TreeNode("Child1");
        TreeNode child2 = new TreeNode("Child2");
        parent1.children.add(child1);
        parent1.children.add(child2);
    }
}

Hint

Use recursion to find height by checking children. For depth, use a helper method to find the node and count levels. A leaf has no children.

4

Print Root, Leaves, Height, Depth, and Level

Print the name of the root. Print the names of all leaf nodes by checking each node. Print the height of the tree using height(root). Print the depth and level (depth + 1) of each node: root, parent1, parent2, child1, and child2. Use System.out.println for output.

DSA Java

Hint

Use System.out.println to print root, leaves, height, and depth/level for each node. Check leaves by calling isLeaf.

Practice

1. In a tree data structure, which node is called the root?

easy

A. The topmost node with no parent

B. A node with no children

C. Any node at the bottom level

D. A node with exactly two children

Solution

1. Step 1: Understand the root node concept

   The root node is the starting point of the tree and has no parent node above it.

2. Step 2: Identify the correct description

   Among the options, only the topmost node with no parent matches the root node definition.

3. Final Answer:

   The topmost node with no parent -> Option A

4. Quick Check:

   Root = topmost node with no parent [OK]

Hint: Root node has no parent, always at the top [OK]

Common Mistakes:

• Confusing root with leaf node
• Thinking root must have children
• Assuming root is any node at bottom

2. Which of the following is the correct way to declare a leaf node in Java if Node is a class representing tree nodes?

easy

A. Node leaf = new Node(); leaf.left = new Node();

B. Node leaf = null; // leaf nodes cannot be null

C. Node leaf = new Node(null, null); // no children

D. Node leaf = new Node(5); // with one child

Solution

1. Step 1: Understand leaf node definition

   A leaf node has no children, so its left and right child references should be null.

2. Step 2: Check each option for leaf node declaration

   Node leaf = new Node(5); // with one child: Node leaf = new Node(5); uses standard constructor which sets left = right = null, creating a leaf node. A adds a child. C likely causes syntax error (no such constructor). D is null, not a node.

3. Final Answer:

   Node leaf = new Node(5); // with no children -> Option D

4. Quick Check:

   Leaf node has no children = left and right null [OK]

Hint: Leaf nodes have no children, so child pointers are null [OK]

Common Mistakes:

• Assuming leaf nodes must have data only
• Creating children for leaf nodes
• Setting leaf node to null reference

3. Consider the following tree structure:

        1
       / \
      2   3
     /   / \
    4   5   6

What is the height of the tree?

medium

A. 5

B. 3

C. 2

D. 4

Solution

1. Step 1: Understand height of a tree

   Height is the number of edges on the longest path from root to a leaf node.

2. Step 2: Find longest path from root (1) to leaf

   Paths: 1->2->4 has 2 edges, 1->3->5 has 2 edges, 1->3->6 has 2 edges. So height = 2.

3. Final Answer:

   2 -> Option C

4. Quick Check:

   Longest path edges = 2 [OK]

Hint: Height = longest edges from root to leaf [OK]

Common Mistakes:

• Counting nodes instead of edges for height
• Confusing height with depth
• Counting root as height 1

4. Given the following code snippet, what is the error?

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

Node root = new Node(10);
root.left = new Node(20);
root.right = new Node(30);
root.left.left = new Node(40);
root.left.right = new Node(50);
root.right.left = new Node(60);
root.right.right = new Node(70);

System.out.println(root.left.right.data);

medium

A. NullPointerException at root.left.right

B. No error, prints 50

C. Syntax error in Node class

D. Prints 60 instead of 50

Solution

1. Step 1: Trace node assignments

   root.left.right is assigned new Node(50), so it exists and has data 50.

2. Step 2: Check print statement

   Printing root.left.right.data will print 50 without error.

3. Final Answer:

   No error, prints 50 -> Option B

4. Quick Check:

   root.left.right.data = 50 [OK]

Hint: Check if node is assigned before accessing data [OK]

Common Mistakes:

• Assuming uninitialized nodes cause error here
• Confusing left and right child nodes
• Thinking print outputs 60

5. In a tree, if the root node is at level 0, what is the depth of the node with value 6 in the tree below?

        1
       / \
      2   3
     /   / \
    4   5   6

medium

A. 2

B. 1

C. 3

D. 4

Solution

1. Step 1: Understand depth definition

   Depth is the number of edges from the root node to the target node.

2. Step 2: Trace path from root (1) to node 6

   Path: 1 -> 3 -> 6 has 2 edges, so depth is 2.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Edges from root to node 6 = 2 [OK]

Hint: Depth = edges from root to node [OK]

Common Mistakes:

• Counting nodes instead of edges for depth
• Confusing depth with level starting at 1
• Assuming depth equals height