Create a Binary Tree Manually in DSA Java - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a binary tree?

A binary tree is a structure where each node has at most two children, called left and right child.

beginner

How do you create a node in a binary tree manually in Java?

You create a node by defining a class with a value and two references: left and right, which point to child nodes or null if no child exists.

beginner

What does the 'null' value represent in a binary tree node's child reference?

It means the node does not have a child on that side (left or right).

beginner

Why do we manually link nodes when creating a binary tree?

Because each node must know its children, so we set the left and right references to build the tree structure.

beginner

What is the root node in a binary tree?

The root node is the top node of the tree from which all other nodes descend.

In a binary tree node, what do the left and right references represent?

A The node's parent

B The node's children

C The node's value

D The node's sibling

Left and right references point to the node's children.

What does it mean if a node's left child is null?

A The node has no left child

B The node has no right child

C The node is the root

D The node is a leaf

Null means no child exists on that side.

Which node is considered the starting point of a binary tree?

A Leaf node

B Right child

C Left child

D Root node

The root node is the top node of the tree.

When creating a binary tree manually, what must you do after creating nodes?

A Link nodes by setting left and right references

B Delete nodes

C Sort nodes

D Convert nodes to arrays

You link nodes by setting their left and right child references.

What is the maximum number of children a binary tree node can have?

A Unlimited

B One

C Two

D Three

Each node can have at most two children: left and right.

Explain how to create a simple binary tree manually in Java.

Think about how each node connects to others.

Describe the role of null in the child references of a binary tree node.

Null is like an empty seat where no child sits.

Practice

1. What is the correct way to create a root node of a binary tree manually in Java using a Node class with an integer value?

easy

A. Node root = new Node(); root.value = 10;

B. Node root = Node(10);

C. Node root = new Node.value(10);

D. Node root = new Node(10);

Solution

1. Step 1: Understand Node object creation

   In Java, to create an object, you use the new keyword followed by the constructor call.

2. Step 2: Apply correct syntax for constructor with value

   The constructor Node(10) creates a node with value 10. So new Node(10) is correct.

3. Final Answer:

   Node root = new Node(10); -> Option D

4. Quick Check:

   Object creation with constructor = new Node(10) [OK]

Hint: Use 'new' keyword with constructor to create objects [OK]

Common Mistakes:

• Omitting 'new' keyword
• Using incorrect constructor syntax
• Trying to assign value without constructor

2. Which of the following is the correct syntax to manually link a left child node with value 5 to a root node in Java?

easy

A. root.left = new Node(5);

B. root.leftNode = new Node(5);

C. root.left = Node(5);

D. root.left = new Node.left(5);

Solution

1. Step 1: Understand node linking in binary tree

   The left child of a node is usually accessed by left field. Assigning a new node requires new Node(value).

2. Step 2: Apply correct field and constructor syntax

   So root.left = new Node(5); correctly creates and links the left child.

3. Final Answer:

   root.left = new Node(5); -> Option A

4. Quick Check:

   Link left child with new Node = root.left = new Node(5) [OK]

Hint: Use 'root.left = new Node(value)' to link left child [OK]

Common Mistakes:

• Using wrong field name like leftNode
• Omitting 'new' keyword
• Incorrect constructor call without 'new'

3. Given the following code, what is the output of an inorder traversal (left, root, right)?

class Node {
  int value;
  Node left, right;
  Node(int v) { value = v; }
}

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);

void inorder(Node node) {
  if (node == null) return;
  inorder(node.left);
  System.out.print(node.value + " ");
  inorder(node.right);
}

inorder(root);

medium

A. 4 2 5 1 3

B. 1 2 3 4 5

C. 1 3 2 4 5

D. 2 4 5 1 3

Solution

1. Step 1: Understand inorder traversal order

   Inorder visits left subtree, then root, then right subtree recursively.

2. Step 2: Trace traversal on given tree

   Left subtree of root(1) is node(2) with children 4 and 5.
   Traverse left subtree of 2: 4 (no children)
   Visit 2
   Traverse right subtree of 2: 5 (no children)
   Visit root 1
   Traverse right subtree of root: 3 (no children)
   Sequence: 4 2 5 1 3

3. Final Answer:

   4 2 5 1 3 -> Option A

4. Quick Check:

   Inorder = left, root, right = 4 2 5 1 3 [OK]

Hint: Inorder = left subtree, root, then right subtree [OK]

Common Mistakes:

• Confusing preorder or postorder with inorder
• Missing left or right subtree nodes
• Printing root before left subtree

4. Identify the error in the following code that tries to create a binary tree manually:

class Node {
  int value;
  Node left, right;
  Node(int v) { value = v; }
}

Node root = new Node(10);
root.left = Node(5);
root.right = new Node(15);

medium

A. Node class constructor is missing

B. Cannot assign right child after root creation

C. Missing 'new' keyword when creating left child node

D. Value type should be String, not int

Solution

1. Step 1: Check node creation syntax

   Creating a new node requires the 'new' keyword before constructor call.

2. Step 2: Identify incorrect line

   Line root.left = Node(5); misses 'new' keyword, causing syntax error.

3. Final Answer:

   Missing 'new' keyword when creating left child node -> Option C

4. Quick Check:

   Object creation needs 'new' keyword [OK]

Hint: Always use 'new' to create objects in Java [OK]

Common Mistakes:

• Omitting 'new' keyword
• Confusing constructor call with method call
• Assuming automatic object creation

5. You want to manually create a binary tree with root value 7, left child 3, right child 9, and left child's right child 5. Which code snippet correctly builds this tree?

hard

A. Node root = new Node(7);
root.left = new Node(3);
root.right = new Node(9);
root.right.left = new Node(5);

B. Node root = new Node(7);
root.left = new Node(3);
root.right = new Node(9);
root.left.right = new Node(5);

C. Node root = new Node(7);
root.left = new Node(3);
root.left.left = new Node(9);
root.left.right = new Node(5);

D. Node root = new Node(7);
root.right = new Node(3);
root.left = new Node(9);
root.left.right = new Node(5);

Solution

1. Step 1: Create root and direct children

   Root is 7, left child 3, right child 9, so assign accordingly.

2. Step 2: Add left child's right child

   Left child's right child is 5, so root.left.right = new Node(5); is correct.

3. Final Answer:

   Node root = new Node(7); root.left = new Node(3); root.right = new Node(9); root.left.right = new Node(5); -> Option B

4. Quick Check:

   Assign children correctly by following tree structure [OK]

Hint: Assign children stepwise matching tree structure [OK]

Common Mistakes:

• Swapping left and right children
• Assigning child to wrong parent node
• Missing intermediate child nodes