Binary Tree Node Structure in DSA Java

Mental Model

A binary tree node holds a value and links to two child nodes, left and right, which can be empty or other nodes.

Analogy: Think of a family tree where each person can have up to two children, one on the left and one on the right, connecting generations.

    [root]
     /   \
 [left] [right]
    ↑       ↑
  node    node

Dry Run Walkthrough

Input: Create a binary tree node with value 10, left child 5, right child 15

Goal: Build a simple binary tree node with two children and show its structure

Step 1: Create root node with value 10

[10] -> left: null, right: null

Why: Start with the root node which holds the main value

Step 2: Create left child node with value 5 and link to root's left

[10] -> left: [5], right: null

Why: Attach left child to root to build the left branch

Step 3: Create right child node with value 15 and link to root's right

[10] -> left: [5], right: [15]

Why: Attach right child to root to build the right branch

Result:

[10] -> left: [5], right: [15]

Annotated Code

DSA Java

public class BinaryTreeNode {
    int value;
    BinaryTreeNode left;
    BinaryTreeNode right;

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

    public static void main(String[] args) {
        BinaryTreeNode root = new BinaryTreeNode(10); // create root node
        root.left = new BinaryTreeNode(5); // create left child
        root.right = new BinaryTreeNode(15); // create right child

        System.out.println("Root value: " + root.value);
        System.out.println("Left child value: " + root.left.value);
        System.out.println("Right child value: " + root.right.value);
    }
}

BinaryTreeNode root = new BinaryTreeNode(10); // create root node

initialize root node with value 10

root.left = new BinaryTreeNode(5); // create left child

link left child node with value 5 to root

root.right = new BinaryTreeNode(15); // create right child

link right child node with value 15 to root

Output

Root value: 10

Left child value: 5

Right child value: 15

Complexity Analysis

Time: O(1) because creating and linking nodes is a constant time operation

Space: O(1) for a single node and its two pointers

vs Alternative: Compared to arrays, binary tree nodes use pointers to link children dynamically without fixed size

Edge Cases

Node with no children (leaf node)

left and right pointers remain null indicating no children

DSA Java

this.left = null;
this.right = null;

Node with only one child

one pointer is null, the other points to the child node

DSA Java

root.left = new BinaryTreeNode(5); // right remains null

When to Use This Pattern

When you need to represent hierarchical data with up to two branches per item, use the binary tree node structure to link values simply.

Common Mistakes

Mistake: Forgetting to initialize left and right pointers to null
Fix: Explicitly set left and right to null in the constructor to avoid unexpected references

Mistake: Confusing left and right child assignments
Fix: Always assign left child to left pointer and right child to right pointer clearly

Summary

It defines a node with a value and two child links for a binary tree.

Use it when building trees where each node can have up to two children.

Remember each node holds data and pointers to left and right children or null if none.

Practice

1. What is the primary purpose of a TreeNode class in a binary tree?

easy

A. To perform tree traversal operations

B. To store only the root node of the tree

C. To store a value and references to left and right child nodes

D. To balance the binary tree automatically

Solution

1. Step 1: Understand the role of a node in a binary tree

   A node holds data and links to its children, enabling tree structure.

2. Step 2: Identify what the TreeNode class stores

   It stores a value and references (pointers) to left and right child nodes.

3. Final Answer:

   To store a value and references to left and right child nodes -> Option C

4. Quick Check:

   Node = value + left + right [OK]

Hint: Nodes hold data and links to children [OK]

Common Mistakes:

• Thinking TreeNode stores the whole tree
• Confusing node with traversal logic
• Assuming TreeNode balances the tree

2. Which of the following is the correct Java syntax to define a binary tree node class with integer data?

easy

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

B. class TreeNode { int data; TreeNode left; TreeNode right; TreeNode(int val) { data = val; } }

C. class TreeNode { int data; TreeNode left; TreeNode right; void TreeNode() {} }

D. class TreeNode { int data; TreeNode left, right; }

Solution

1. Step 1: Check class field declarations

   Fields for data, left, and right nodes must be declared properly.

2. Step 2: Verify constructor syntax

   Constructor should initialize data; class TreeNode { int data; TreeNode left; TreeNode right; TreeNode(int val) { data = val; } } correctly defines constructor.

3. Final Answer:

   class TreeNode { int data; TreeNode left; TreeNode right; TreeNode(int val) { data = val; } } -> Option B

4. Quick Check:

   Constructor initializes data correctly [OK]

Hint: Constructor must initialize data field [OK]

Common Mistakes:

• Missing constructor to set data
• Incorrect constructor syntax (void TreeNode())
• Declaring multiple variables incorrectly

3. Given the following code, what will be printed?

class TreeNode {
  int data;
  TreeNode left, right;
  TreeNode(int val) { data = val; }
}

public class Main {
  public static void main(String[] args) {
    TreeNode root = new TreeNode(10);
    root.left = new TreeNode(5);
    root.right = new TreeNode(15);
    System.out.println(root.left.data + "," + root.right.data);
  }
}

medium

A. 5,15

B. 10,5

C. 15,5

D. 10,15

Solution

1. Step 1: Create root node with data 10

   Root node data is 10, left and right are null initially.

2. Step 2: Assign left and right children with data 5 and 15

   root.left.data = 5, root.right.data = 15.

3. Step 3: Print left and right data

   Output is "5,15" from root.left.data and root.right.data.

4. Final Answer:

   5,15 -> Option A

5. Quick Check:

   Left=5, Right=15 [OK]

Hint: Print left and right node data directly [OK]

Common Mistakes:

• Printing root data instead of children
• Swapping left and right values
• Confusing node references

4. Identify the error in the following TreeNode class code:

class TreeNode {
  int data;
  TreeNode left, right;
  void TreeNode(int val) {
    data = val;
  }
}

medium

A. Constructor has void return type, so it's a method not a constructor

B. Missing semicolon after data declaration

C. left and right should be arrays, not single nodes

D. Class name and constructor name do not match

Solution

1. Step 1: Check constructor syntax

   Constructor should not have a return type; 'void' makes it a method.

2. Step 2: Confirm class and constructor names match

   Names match, so no error there.

3. Final Answer:

   Constructor has void return type, so it's a method not a constructor -> Option A

4. Quick Check:

   Constructor no return type [OK]

Hint: Constructor must not have a return type [OK]

Common Mistakes:

• Adding void before constructor name
• Confusing methods with constructors
• Thinking left/right must be arrays

5. You want to create a binary tree node class that also stores a parent node reference. Which of the following class definitions correctly adds this feature?

hard

A. class TreeNode { int data; TreeNode left, right, parent; TreeNode(int val) { data = val; } }

B. class TreeNode { int data; TreeNode left, right; TreeNode parent; TreeNode(int val) { data = val; parent = null; } }

C. class TreeNode { int data; TreeNode left, right; TreeNode parent; TreeNode(int val) { data = val; left = right = parent = null; } }

D. class TreeNode { int data; TreeNode left, right; TreeNode parent; TreeNode(int val, TreeNode p) { data = val; parent = p; } }

Solution

1. Step 1: Understand the need for parent reference initialization

   Parent reference should be set when node is created to link properly.

2. Step 2: Check constructor parameters and assignments

   class TreeNode { int data; TreeNode left, right; TreeNode parent; TreeNode(int val, TreeNode p) { data = val; parent = p; } } passes parent node as parameter and assigns it correctly.

3. Final Answer:

   class TreeNode { int data; TreeNode left, right; TreeNode parent; TreeNode(int val, TreeNode p) { data = val; parent = p; } } -> Option D

4. Quick Check:

   Parent passed and assigned in constructor [OK]

Hint: Pass parent node in constructor to set reference [OK]

Common Mistakes:

• Not initializing parent reference
• Setting parent to null always
• Declaring parent but never assigning