Create a Binary Tree Manually in DSA Java

Mental Model

A binary tree is a structure where each node can have up to two children, left and right. Creating it manually means linking nodes one by one to build the tree.

Analogy: Think of a family tree where each person can have up to two children. You create the family tree by connecting parents to their children step by step.

    1
   / \
  2   3
 / \
4   5

Dry Run Walkthrough

Input: Create a binary tree with root 1, left child 2, right child 3, and 2's children 4 and 5

Goal: Build the binary tree by manually linking nodes to form the structure

Step 1: Create root node with value 1

1 (root) ↑

Why: Start with the root node as the base of the tree

Step 2: Create node with value 2 and link as left child of root

    1
   / 
  2 ↑

Why: Add left child to root to build left subtree

Step 3: Create node with value 3 and link as right child of root

    1
   / \
  2   3 ↑

Why: Add right child to root to complete root's children

Step 4: Create node with value 4 and link as left child of node 2

    1
   / \
  2   3
 / 
4 ↑

Why: Build left subtree further by adding left child to node 2

Step 5: Create node with value 5 and link as right child of node 2

    1
   / \
  2   3
 / \
4   5 ↑

Why: Complete left subtree by adding right child to node 2

Result:

    1
   / \
  2   3
 / \
4   5

Tree created with root 1 and children 2,3; 2 has children 4,5

Annotated Code

DSA Java

class Node {
    int value;
    Node left, right;

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

public class BinaryTreeManual {
    public static void main(String[] args) {
        // Step 1: Create root node
        Node root = new Node(1);

        // Step 2: Create left child of root
        root.left = new Node(2);

        // Step 3: Create right child of root
        root.right = new Node(3);

        // Step 4: Create left child of node 2
        root.left.left = new Node(4);

        // Step 5: Create right child of node 2
        root.left.right = new Node(5);

        // Print tree structure
        printTree(root, "");
    }

    // Helper method to print tree nodes
    static void printTree(Node node, String indent) {
        if (node == null) return;
        System.out.println(indent + node.value);
        printTree(node.left, indent + "  ");
        printTree(node.right, indent + "  ");
    }
}

Node root = new Node(1);

Create root node as starting point of tree

root.left = new Node(2);

Link left child to root node

root.right = new Node(3);

Link right child to root node

root.left.left = new Node(4);

Link left child to node 2

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

Link right child to node 2

printTree(root, "");

Recursively print tree nodes in preorder

Output

1

  2

    4

    5

  3

Complexity Analysis

Time: O(n) because we create and print each of the n nodes once

Space: O(n) because we store n nodes in memory and recursion stack can go up to height n

vs Alternative: Manual creation is straightforward but verbose; automated tree builders or input parsers can create trees faster for large data

Edge Cases

Empty tree (no nodes)

No nodes created, print function exits immediately

DSA Java

if (node == null) return;

Single node tree (only root)

Only root node created and printed

DSA Java

Node root = new Node(1);

When to Use This Pattern

When you need to build a binary tree from scratch or fixed values, manually linking nodes is the pattern to use because it gives full control over structure.

Common Mistakes

Mistake: Forgetting to link child nodes to their parents
Fix: Always assign child nodes to parent's left or right pointer explicitly

Mistake: Confusing left and right child assignments
Fix: Remember left child is assigned to left pointer, right child to right pointer

Summary

Manually create a binary tree by making nodes and linking them as left and right children.

Use this when you want to build a specific tree structure step by step.

The key is to create nodes first, then connect them by setting left and right pointers.

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