Binary Tree Node Structure in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a binary tree node?

A binary tree node is a basic unit of a binary tree that contains data and references to at most two child nodes: left and right.

beginner

What are the main parts of a binary tree node?

A binary tree node has three main parts:

• Data: stores the value.
• Left child: reference to the left subtree.
• Right child: reference to the right subtree.

beginner

TypeScript code snippet: Define a simple binary tree node class.

class TreeNode {
  value: number;
  left: TreeNode | null;
  right: TreeNode | null;

  constructor(value: number) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

beginner

Why do left and right child references sometimes hold null?

Because a node may not have a left or right child, so the reference is set to null to show the absence of a child node.

beginner

How does a binary tree node relate to real-life family trees?

Like a person in a family tree has parents and children, a binary tree node has a value and can have up to two children nodes, representing branches.

What does a binary tree node typically contain?

A Only data

B Only two child references

C Data and three child references

D Data and two child references

A binary tree node contains data and references to at most two children: left and right.

In TypeScript, what type should the left and right child references have in a binary tree node?

A number

B TreeNode | null

C string

D boolean

Left and right children can be either another TreeNode or null if no child exists.

If a node has no left child, what is the left reference set to?

A 0

B undefined

C null

D empty string

Null is used to indicate the absence of a child node.

How many children can a binary tree node have at most?

A Two

B One

C Three

D Unlimited

By definition, a binary tree node can have up to two children.

Which of these is NOT a part of a binary tree node?

A Parent reference

B Data value

C Left child reference

D Right child reference

A basic binary tree node does not usually store a parent reference.

Describe the structure of a binary tree node and its components.

Think about what each node holds and how it connects to others.

Explain why left and right child references can be null in a binary tree node.

Consider what happens when a node has no children.

Practice

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

easy

A. Only a value and a pointer to the next node

B. A value, a left child node, and a right child node

C. A value and multiple child nodes in a list

D. Only a value without any child nodes

Solution

1. Step 1: Understand binary tree node components

   A binary tree node typically stores a value and references to two children: left and right.

2. Step 2: Compare options with definition

   A value, a left child node, and a right child node correctly lists value, left child, and right child. Others describe linked list or general tree nodes.

3. Final Answer:

   A value, a left child node, and a right child node -> Option B

4. Quick Check:

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

Hint: Binary tree nodes always have two child pointers [OK]

Common Mistakes:

• Confusing binary tree node with linked list node
• Thinking nodes have multiple children like general trees
• Ignoring child pointers in node structure

2. Which of the following is the correct TypeScript syntax to define a binary tree node class?

easy

A. class Node { value: number; left: Node | undefined; right: Node | undefined; constructor(value: number) { this.value = value; this.left = null; this.right = null; } }

B. class Node { value: number; left: Node; right: Node; constructor(value: number) { this.value = value; } }

C. class Node { value: number; left: Node | null; right: Node | null; constructor(value: number) { this.value = value; this.left = null; this.right = null; } }

D. class Node { value: number; left: Node | null; right: Node | null; constructor() { this.value = 0; this.left = null; this.right = null; } }

Solution

1. Step 1: Check property types and initialization

   class Node { value: number; left: Node | null; right: Node | null; constructor(value: number) { this.value = value; this.left = null; this.right = null; } } correctly declares left and right as Node or null and initializes them to null in constructor.

2. Step 2: Verify constructor parameters and assignments

   class Node { value: number; left: Node | null; right: Node | null; constructor(value: number) { this.value = value; this.left = null; this.right = null; } } constructor takes value and sets left and right to null, matching typical binary tree node setup.

3. Final Answer:

   Correct TypeScript class with nullable children and proper constructor -> Option C

4. Quick Check:

   Nullable children + constructor with value = class Node { value: number; left: Node | null; right: Node | null; constructor(value: number) { this.value = value; this.left = null; this.right = null; } } [OK]

Hint: Child nodes must allow null to represent empty branches [OK]

Common Mistakes:

• Not initializing left and right to null
• Using undefined instead of null for children
• Missing constructor parameter for value

3. Given the following TypeScript code, what will be the output of console.log(root.left?.value)?

class Node {
  value: number;
  left: Node | null;
  right: Node | null;
  constructor(value: number) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}
const root = new Node(10);
root.left = new Node(5);
root.right = new Node(15);
console.log(root.left?.value);

medium

A. 5

B. undefined

C. null

D. 10

Solution

1. Step 1: Analyze node assignments

   root.left is assigned a new Node with value 5, so root.left is not null.

2. Step 2: Understand optional chaining and output

   Using root.left?.value safely accesses value of left node, which is 5.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   root.left.value = 5 [OK]

Hint: Optional chaining returns value if node exists, else undefined [OK]

Common Mistakes:

• Confusing null and undefined outputs
• Assuming root.left is null by default
• Misreading optional chaining operator

4. Identify the error in this TypeScript binary tree node class and fix it:

class Node {
  value: number;
  left: Node;
  right: Node;
  constructor(value: number) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

medium

A. left and right should allow null type (Node | null)

B. Constructor should not assign null to left and right

C. value should be optional in constructor

D. Class should not have a constructor

Solution

1. Step 1: Check property types vs assigned values

   left and right are typed as Node but assigned null, causing type error.

2. Step 2: Fix type declarations

   Change left and right types to Node | null to allow null assignment.

3. Final Answer:

   left and right should allow null type (Node | null) -> Option A

4. Quick Check:

   Nullable children fix type error [OK]

Hint: Child nodes must be nullable if assigned null [OK]

Common Mistakes:

• Not updating types when assigning null
• Removing constructor unnecessarily
• Making value optional without reason

5. How would you modify the binary tree node class to include a parent pointer, and what is the impact on tree traversal?

hard

A. No changes needed; parent pointer is implicit in left and right

B. Add a parent property of type number; no impact on traversal

C. Add a parent property as an array of nodes; allows multiple parents

D. Add a parent property of type Node | null; allows upward traversal from child to parent

Solution

1. Step 1: Understand parent pointer addition

   Adding a parent property of type Node | null stores reference to parent node.

2. Step 2: Impact on traversal

   This allows traversing upwards from child to parent, enabling bidirectional navigation.

3. Final Answer:

   Add a parent property of type Node | null; allows upward traversal from child to parent -> Option D

4. Quick Check:

   Parent pointer enables upward traversal [OK]

Hint: Parent pointer lets you move up the tree easily [OK]

Common Mistakes:

• Using wrong type for parent pointer
• Assuming parent pointer exists by default
• Confusing parent pointer with multiple parents