Why Trees Exist and What Linked Lists and Arrays Cannot Do in DSA Java - See It Work

Why Trees Exist and What Linked Lists and Arrays Cannot Do

📖 Scenario: Imagine you are organizing a family reunion. You want to keep track of family members and their relationships. Using simple lists or arrays makes it hard to show who is whose parent or child. Trees help us show these family connections clearly.

🎯 Goal: You will build a simple family tree using nodes connected like a tree. You will see why linked lists and arrays cannot easily show these relationships.

📋 What You'll Learn

Create a class called FamilyMember with a String name and a list of children

Create a root FamilyMember called grandparent with name "Grandparent"

Add two children to grandparent: "Parent1" and "Parent2"

Add one child to "Parent1": "Child1"

Print the family tree showing names and their children

💡 Why This Matters

🌍 Real World

Trees are used to represent hierarchical data like family trees, company structures, file systems, and more.

💼 Career

Understanding trees helps in software development roles involving data organization, search algorithms, and UI component trees.

1

Create the FamilyMember class and root node

Create a class called FamilyMember with a String name and a List<FamilyMember> children. Then create a FamilyMember object called grandparent with the name "Grandparent".

DSA Java

// Define FamilyMember class and create grandparent
// Your code here

Hint

Use ArrayList to create the list of children inside the FamilyMember class.

2

Add children to the grandparent

Add two children to grandparent by creating FamilyMember objects named parent1 with name "Parent1" and parent2 with name "Parent2". Then add both to grandparent.children.

DSA Java

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

class FamilyMember {
    String name;
    List children;

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

public class FamilyTree {
    public static void main(String[] args) {
        FamilyMember grandparent = new FamilyMember("Grandparent");
        // Create parent1 and parent2 and add to grandparent.children
        // Your code here
    }
}

Hint

Create two new FamilyMember objects and add them to the children list of grandparent.

3

Add a child to Parent1

Create a FamilyMember called child1 with name "Child1" and add it to parent1.children.

DSA Java

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

class FamilyMember {
    String name;
    List children;

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

public class FamilyTree {
    public static void main(String[] args) {
        FamilyMember grandparent = new FamilyMember("Grandparent");
        FamilyMember parent1 = new FamilyMember("Parent1");
        FamilyMember parent2 = new FamilyMember("Parent2");
        grandparent.children.add(parent1);
        grandparent.children.add(parent2);
        // Create child1 and add to parent1.children
        // Your code here
    }
}

Hint

Create a new FamilyMember for the child and add it to the children list of parent1.

4

Print the family tree

Write a method called printFamily that takes a FamilyMember and prints the member's name and their children names indented. Then call printFamily(grandparent, 0) to display the whole tree.

DSA Java

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

class FamilyMember {
    String name;
    List children;

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

public class FamilyTree {
    public static void printFamily(FamilyMember member, int level) {
        // Your code here
    }

    public static void main(String[] args) {
        FamilyMember grandparent = new FamilyMember("Grandparent");
        FamilyMember parent1 = new FamilyMember("Parent1");
        FamilyMember parent2 = new FamilyMember("Parent2");
        grandparent.children.add(parent1);
        grandparent.children.add(parent2);
        FamilyMember child1 = new FamilyMember("Child1");
        parent1.children.add(child1);
        // Call printFamily here
        // Your code here
    }
}

Hint

Use recursion to print each member's name with indentation based on level. Then print all children with level + 1.

Practice

1. Why do trees exist as a data structure when we already have arrays and linked lists?

easy

A. Because trees are easier to implement than arrays and linked lists

B. Because trees use less memory than arrays and linked lists

C. Because trees allow hierarchical data representation which arrays and linked lists cannot efficiently provide

D. Because trees always provide faster access than arrays and linked lists

Solution

1. Step 1: Understand the limitation of arrays and linked lists

   Arrays and linked lists store data linearly, which makes representing hierarchical relationships difficult and inefficient.

2. Step 2: Identify the advantage of trees

   Trees naturally represent hierarchical data, like file systems or organizational charts, allowing efficient parent-child relationships.

3. Final Answer:

   Trees allow hierarchical data representation which arrays and linked lists cannot efficiently provide -> Option C

4. Quick Check:

   Hierarchical data needs trees [OK]

Hint: Trees represent hierarchy; arrays and lists are linear [OK]

Common Mistakes:

• Thinking trees always use less memory
• Assuming trees are simpler to implement
• Believing trees always have faster access

2. Which of the following is the correct way to declare a simple binary tree node class in Java?

easy

A. class Node { int data; Node left; Node right; }

B. class Node { int data; Node next; Node prev; }

C. class Node { int data; Node child; }

D. class Node { int data; Node[] children; }

Solution

1. Step 1: Identify binary tree node structure

   A binary tree node has data and two child references: left and right.

2. Step 2: Match the correct class declaration

   class Node { int data; Node left; Node right; } declares int data and two Node references named left and right, matching binary tree structure.

3. Final Answer:

   class Node { int data; Node left; Node right; } -> Option A

4. Quick Check:

   Binary tree node = data + left + right [OK]

Hint: Binary tree nodes have left and right children only [OK]

Common Mistakes:

• Using next and prev which are for linked lists
• Using only one child reference
• Using an array for children in binary tree

3. What will be the output of the following Java code that builds a simple tree and prints the root's left child's data?

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

public class TestTree {
  public static void main(String[] args) {
    Node root = new Node(10);
    root.left = new Node(20);
    root.right = new Node(30);
    System.out.println(root.left.data);
  }
}

medium

A. 10

B. 20

C. 30

D. NullPointerException

Solution

1. Step 1: Trace tree node creation

   Root node has data 10; root.left is assigned a new node with data 20; root.right is assigned 30.

2. Step 2: Identify printed value

   System.out.println prints root.left.data, which is 20.

3. Final Answer:

   20 -> Option B

4. Quick Check:

   root.left.data = 20 [OK]

Hint: Print root.left.data to get left child's value [OK]

Common Mistakes:

• Printing root.data instead of root.left.data
• Confusing left and right child
• Expecting NullPointerException without initialization

4. Find the error in the following code snippet that tries to create a binary tree node and assign its children:

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

public class TreeTest {
  public static void main(String[] args) {
    Node root = new Node(5);
    root.left.data = 3;
    root.right.data = 7;
  }
}

medium

A. Class Node should be public

B. Node constructor is missing parameters

C. Data type of data is incorrect

D. root.left and root.right are not initialized before accessing data

Solution

1. Step 1: Check initialization of child nodes

   root.left and root.right are declared but never assigned new Node objects, so they are null.

2. Step 2: Identify cause of error

   Accessing root.left.data causes NullPointerException because root.left is null.

3. Final Answer:

   root.left and root.right are not initialized before accessing data -> Option D

4. Quick Check:

   NullPointerException due to uninitialized children [OK]

Hint: Always initialize child nodes before accessing their fields [OK]

Common Mistakes:

• Assuming constructor error causes problem
• Thinking data type int is wrong
• Believing class visibility causes runtime error

5. You want to store a company's organizational chart where each manager can have multiple direct reports. Which data structure is best suited and why can't arrays or linked lists alone handle this efficiently?

hard

A. Use a tree because it naturally models hierarchical relationships; arrays and linked lists are linear and can't represent multiple levels easily

B. Use an array because it allows fast access to all employees; linked lists and trees are too slow

C. Use a linked list because it can store multiple reports in sequence; arrays and trees are not flexible

D. Use a graph because trees cannot represent multiple reports; arrays and linked lists are sufficient

Solution

1. Step 1: Understand organizational chart structure

   It is hierarchical with managers having multiple direct reports, forming a tree-like structure.

2. Step 2: Evaluate data structure suitability

   Trees represent hierarchy with parent-child links; arrays and linked lists are linear and cannot represent multiple levels or branches efficiently.

3. Final Answer:

   Use a tree because it naturally models hierarchical relationships; arrays and linked lists are linear and can't represent multiple levels easily -> Option A

4. Quick Check:

   Hierarchy needs trees, not linear arrays/lists [OK]

Hint: Hierarchy = tree; linear structures can't model multiple levels [OK]

Common Mistakes:

• Choosing arrays for hierarchical data
• Confusing linked lists as hierarchical
• Thinking graphs are needed for simple hierarchy