Return Binary Search Tree Values in Ascending Order

Question

The candidate is asked to implement a function that returns the values of a binary search tree (BST) in ascending order.

Codemia · Accepted Answer

To return the values of a binary search tree in ascending order, we need to leverage the properties of a BST. In a BST, for any given node, the left subtree contains only nodes with values less than the node's value, and the right subtree contains only nodes with values greater than the node's value. This property allows us to perform an in-order traversal, which visits nodes in ascending order.

The in-order traversal can be implemented using either recursion or iteration. The recursive approach is more straightforward:

1. Traverse the left subtree.
2. Visit the current node and record its value.
3. Traverse the right subtree.

This ensures that we visit nodes in ascending order. Let's implement this in Python.

Here is a Python implementation of the in-order traversal:

```python
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def inorderTraversal(root):
    result = []
    def traverse(node):
        if node:
            traverse(node.left)
            result.append(node.val)
            traverse(node.right)
    traverse(root)
    return result
```
This function initializes an empty list `result`, defines a nested function `traverse` for the recursive traversal, and finally returns the collected values.

The time complexity of the in-order traversal is O(n), where n is the number of nodes in the tree, because we visit each node exactly once. The space complexity is O(h), where h is the height of the tree. In the case of a balanced tree, this is O(log n), but in the worst case of an unbalanced tree, it can be O(n).

It's important to handle edge cases, such as when the tree is empty. In such cases, we should return an empty list. Overall, the in-order traversal is a fundamental technique for working with binary search trees and is essential for retrieving values in sorted order.

Return Binary Search Tree Values in Ascending Order

Moody's

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Understanding the Problem

In-Order Traversal Approach

Submit Your Answer

Moody's Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string