Why Trees Exist and What Linked Lists and Arrays Cannot Do in DSA Java - Test Your Knowledge

Practice - 5 Tasks

1fill in blank

easy

Complete the code to create a root node for a binary tree.

DSA Java

TreeNode root = new TreeNode([1]);

Drag options to blanks, or click blank then click option'

A10

B"root"

Cnull

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using a string instead of a number

Using null as a value

The root node value should be an integer, so 10 is correct.

2fill in blank

medium

Complete the code to link the left child node to the root.

DSA Java

root.left = new TreeNode([1]);

Drag options to blanks, or click blank then click option'

A"left"

Bnull

C5

Droot

Attempts:

3 left

💡 Hint

Common Mistakes

Assigning null instead of a node

Using the root variable as a value

The left child node should have a numeric value, so 5 is correct.

3fill in blank

hard

Fix the error in the code to add a right child node.

DSA Java

root.right = new TreeNode([1]);

Drag options to blanks, or click blank then click option'

Anull

B15

Croot

D"right"

Attempts:

3 left

💡 Hint

Common Mistakes

Using null as a value

Assigning the root node as a value

The right child node should have a numeric value, so 15 is correct.

4fill in blank

hard

Fill both blanks to create a method that checks if a node has children.

DSA Java

public boolean hasChildren(TreeNode node) {
    return node.[1] != null || node.[2] != null;
}

Drag options to blanks, or click blank then click option'

Aleft

Bright

Cvalue

Dparent

Attempts:

3 left

💡 Hint

Common Mistakes

Checking value or parent instead of children

Checking only one child

To check if a node has children, we check if left or right child is not null.

5fill in blank

hard

Fill all three blanks to create a method that counts nodes in a binary tree.

DSA Java

public int countNodes(TreeNode [1]) {
    if ([2] == null) return 0;
    return 1 + countNodes([3].left) + countNodes([3].right);
}

Drag options to blanks, or click blank then click option'

Aroot

Bnode

Attempts:

3 left

💡 Hint

Common Mistakes

Using different variable names inconsistently

Not checking for null

The method uses 'node' as the parameter and variable to count nodes recursively.

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