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

Recall & Review

beginner

What is a Binary Search Tree (BST)?

A Binary Search Tree is a tree data structure where each node has at most two children. For every node, all nodes in its left subtree have smaller values, and all nodes in its right subtree have larger values.

beginner

How do you find the maximum element in a BST?

To find the maximum element in a BST, start at the root and keep moving to the right child until you reach a node with no right child. That node contains the maximum value.

beginner

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

Because in a BST, all values in the right subtree are greater than the current node. So, moving right keeps going to larger values until no more right child exists, which is the maximum.

intermediate

What is the time complexity of finding the maximum element in a BST?

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

beginner

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

Node* findMax(Node* root) { if (root == nullptr) return nullptr; while (root->right != nullptr) { root = root->right; } return root; }

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 all right children have larger values.

What should you do if the BST is empty when finding the maximum element?

A Return root

B Return null or nullptr

C Return minimum element

D Throw an error

If the BST is empty (root is null), there is no maximum element, so return null or nullptr.

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

A O(1)

B O(n)

C O(log n)

D O(n log n)

In a balanced BST, the height is about log n, so finding the maximum element takes O(log n) time.

Which pointer do you follow to find the maximum element in a BST?

A Right child pointer

B Parent pointer

C Left child pointer

D Random pointer

You follow the right child pointer repeatedly to reach the maximum element.

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

A Right child

B No maximum element

C Left child

D The root node itself

If there is only one node, that node is both the minimum and maximum element.

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

Think about the BST property and the direction to move.

Write a simple C++ function to find the maximum element in a BST and explain its logic.

Use a while loop to traverse right children.