BST Find Maximum Element in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a Binary Search Tree (BST)?

A BST is a tree where each node has at most two children. The left child's value is less than the node's value, and the right child's value is greater. This helps in fast searching.

beginner

How do you find the maximum element in a BST?

Start at the root and keep moving to the right child until there is no right child. The last node you reach is the maximum element.

beginner

Why does moving right in a BST lead to the maximum element?

Because in a BST, all right children have values greater than their parents, so the rightmost node holds the largest value.

intermediate

What is the time complexity to find the maximum element in a BST?

The time complexity is O(h), where h is the height of the tree. In the worst case (skewed tree), it can be O(n), and in a balanced tree, it is O(log n).

intermediate

Show the TypeScript code snippet to find the maximum element in a BST.

function findMax(root: TreeNode | null): number | null {
  if (!root) return null;
  let current = root;
  while (current.right) {
    current = current.right;
  }
  return current.val;
}

In a BST, where is the maximum element located?

A Rightmost node

B Leftmost node

C Root node

D Any leaf node

The maximum element is always the rightmost node in a BST because right children have greater values.

What is the first step to find the maximum element in a BST?

A Move to the left child

B Move to the right child

C Check the root value

D Traverse all nodes

You start at the root and move to the right child repeatedly to find the maximum.

What is the time complexity to find the maximum element in a balanced BST?

A O(n)

B O(1)

C O(log n)

D O(n log n)

In a balanced BST, height is log n, so finding max takes O(log n) time.

If a BST has only one node, what is the maximum element?

A The root node's value

B Null

C The left child's value

D The right child's value

With one node, that node is both minimum and maximum.

Which of these is NOT true about finding the maximum in a BST?

A You always move right to find the max

B The max is the rightmost node

C The max is greater than all other nodes

D You must check all nodes to find the max

You do not need to check all nodes; just follow the right children.

Explain step-by-step how to find the maximum element in a BST.

Think about the BST property of right children.

Write a simple TypeScript function to find the maximum element in a BST and explain how it works.

Use a while loop to traverse right children.