Binary Tree Node Structure in DSA C#

Mental Model

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

Analogy: Think of a family tree where each person can have up to two children, and each child can have their own children, forming branches.

    [Root]
    /    \
 [Left]  [Right]
   ↑       ↑
  null    null

Dry Run Walkthrough

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

Goal: Build a binary tree node that connects to two child nodes correctly

Step 1: Create root node with value 10 and no children

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

Why: Start with the root node before adding children

Step 2: Create left child node with value 5

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

Why: Add left child to root node

Step 3: Create right child node with value 15

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

Why: Add right child to root node

Result:

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

Annotated Code

DSA C#

using System;

public class TreeNode
{
    public int Value;
    public TreeNode Left;
    public TreeNode Right;

    public TreeNode(int value)
    {
        Value = value;
        Left = null;
        Right = null;
    }
}

public class Program
{
    public static void Main()
    {
        // Step 1: Create root node
        TreeNode root = new TreeNode(10);

        // Step 2: Create left child
        root.Left = new TreeNode(5);

        // Step 3: Create right child
        root.Right = new TreeNode(15);

        // Print tree structure
        PrintNode(root);
    }

    public static void PrintNode(TreeNode node)
    {
        if (node == null) return;
        Console.WriteLine($"Node Value: {node.Value}");
        Console.WriteLine($" Left Child: {(node.Left != null ? node.Left.Value.ToString() : "null")}");
        Console.WriteLine($" Right Child: {(node.Right != null ? node.Right.Value.ToString() : "null")}");
    }
}

TreeNode root = new TreeNode(10);

Create root node with value 10 and no children

root.Left = new TreeNode(5);

Assign left child node with value 5 to root

root.Right = new TreeNode(15);

Assign right child node with value 15 to root

Output

Node Value: 10

 Left Child: 5

 Right Child: 15

Complexity Analysis

Time: O(1) because creating a node and assigning children are constant time operations

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

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

Edge Cases

Node with no children (leaf node)

Left and right pointers remain null, representing no further branches

DSA C#

Left = null; Right = null;

Node with only one child

One child pointer is assigned, the other remains null, allowing partial branches

DSA C#

root.Left = new TreeNode(5); // Right remains null

When to Use This Pattern

When you need to represent hierarchical data with up to two children per item, use the binary tree node structure to link nodes efficiently.

Common Mistakes

Mistake: Forgetting to initialize left and right child pointers to null
Fix: Explicitly set Left and Right to null in the constructor to avoid undefined references

Mistake: Assigning child nodes incorrectly, such as swapping left and right
Fix: Carefully assign left and right children to their correct pointers to maintain tree structure

Summary

A binary tree node holds a value and links to two child nodes, left and right.

Use it to build tree structures where each node can have up to two children.

The key is each node points to its children, forming branches like a family tree.

Practice

1. What does a typical binary tree node contain in its structure?

easy

A. Only a value without any references

B. A value and a reference to the next node in a list

C. References to parent and sibling nodes only

D. A value and references to left and right child nodes

Solution

1. Step 1: Understand binary tree node components

   A binary tree node stores data and links to its children nodes.

2. Step 2: Identify correct node structure

   It must have a value and two references: one for left child and one for right child.

3. Final Answer:

   A value and references to left and right child nodes -> Option D

4. Quick Check:

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

Hint: Remember: binary tree nodes have two child links [OK]

Common Mistakes:

• Thinking nodes only store values without links
• Confusing with linked list node structure
• Assuming nodes have parent or sibling references by default

2. Which of the following is the correct C# syntax to declare a binary tree node class with integer value and left/right children?

easy

A. public struct Node { int val; Node left; Node right; }

B. class Node { int val; Node left, right; }

C. public class Node { public int val; public Node left; public Node right; }

D. public class Node { int val; Node left; Node right; void Node() {} }

Solution

1. Step 1: Check access modifiers and field declarations

   Public class with public fields allows access outside the class, correct for node structure.

2. Step 2: Validate syntax correctness

   public class Node { public int val; public Node left; public Node right; } uses public class, public int val, and public Node left/right fields correctly.

3. Final Answer:

   public class Node { public int val; public Node left; public Node right; } -> Option C

4. Quick Check:

   Public class with public fields = public class Node { public int val; public Node left; public Node right; } [OK]

Hint: Use public class and public fields for node structure [OK]

Common Mistakes:

• Missing public keyword causing access issues
• Using struct instead of class for nodes
• Incorrect constructor syntax or missing access modifiers

3. Given the following code, what will be the output when printing the root node's left child's value?

public class Node {
  public int val;
  public Node left;
  public Node right;
  public Node(int v) { val = v; }
}

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

medium

A. 5

B. null

C. 15

D. 10

Solution

1. Step 1: Trace node assignments

   Root node value is 10, left child assigned new Node with value 5.

2. Step 2: Identify printed value

   Printing root.left.val outputs 5, the left child's value.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   root.left.val = 5 [OK]

Hint: Print left child's val to get 5 [OK]

Common Mistakes:

• Printing root.val instead of root.left.val
• Confusing left and right child values
• Assuming uninitialized children print null

4. Identify the error in the following binary tree node class code:

public class Node {
  public int val;
  public Node left, right;
  public Node(int value) {
    val = value;
    left = null;
    right = null;
  }
}

Node root = new Node(10);
root.left.val = 5;

medium

A. Cannot assign val to left child before initializing left node

B. Constructor missing return type

C. left and right should be private fields

D. Node class should be a struct

Solution

1. Step 1: Analyze node initialization

   left and right are initialized to null in constructor, so root.left is null initially.

2. Step 2: Check assignment to left.val

   Trying to assign root.left.val = 5 causes null reference error because root.left is null.

3. Final Answer:

   Cannot assign val to left child before initializing left node -> Option A

4. Quick Check:

   Assigning to null child causes error [OK]

Hint: Initialize child node before assigning its value [OK]

Common Mistakes:

• Assuming child nodes auto-initialize
• Ignoring null reference exceptions
• Confusing constructor syntax errors

5. How would you modify the binary tree node class to include a method that returns true if the node is a leaf (has no children)?

hard

A. public bool IsLeaf() { return val == null; }

B. public bool IsLeaf() { return left == null && right == null; }

C. public bool IsLeaf() { return left != null || right != null; }

D. public bool IsLeaf() { return left == right; }

Solution

1. Step 1: Define leaf node condition

   A leaf node has no left or right children, so both must be null.

2. Step 2: Write method to check children

   Return true if left and right are null, false otherwise.

3. Final Answer:

   public bool IsLeaf() { return left == null && right == null; } -> Option B

4. Quick Check:

   Leaf check = left and right null [OK]

Hint: Leaf means no children: left and right null [OK]

Common Mistakes:

• Checking value instead of children
• Using OR instead of AND in condition
• Comparing left and right references directly