Problem

Given Preorder traversal of a BST, check if each non-leaf node has only one child. Assume that the BST contains unique entries.

Examples

Example 1

graph TD
    A(8)
    A --- B(3)
    A ~~~ N1:::hidden
    B --- C(2)
    B ~~~ N2:::hidden
    C ~~~ N3:::hidden
    C --- D(6)

classDef hidden display:none
  
1
2
3

Input: preorder = [8, 3, 2, 6]
Output: True
Explanation: The BST constructed has 8 -> 3 -> 2 -> 6. Each non-leaf node (8 and 3) has exactly one child.

Example 2

graph TD
    A(8)
    A --- B(3)
    A ~~~ N1:::hidden
    B --- C(2)
    B --- D(6)

classDef hidden display:none
  
1
2
3

Input: preorder = [8, 3, 6, 2]
Output: True
Explanation: The BST constructed has 8 -> 3 -> 2 -> 6. Each non-leaf node (8 and 3) has exactly one child.

Solution

This problem revolves around properties of a BST and its preorder traversal. In a BST:

  • Nodes are visited in the order: root -> left subtree -> right subtree.

Now, if each - non-leaf node has only one child, then adjacencies in the array represent a path either entirely increasing (right children only) or entirely decreasing (left children only).

For e.g. for node 8, all the descendants are smaller than 8, as they all appear on left of 8. Similarly, for node 2, all its descendants are greater than 2, and they all appear on the right of 2.

This is because, in a BST with only one child per node, every descendant will lie on either the left or right subtree, leading to this consistent behaviour.

Method 1 - Naive

This approach is based on the idea that all values to the right of a node are either smaller or larger. It uses two loops: the outer loop iteratively selects each element starting from the leftmost, and the inner loop verifies whether all elements to the right of the selected element are either smaller or larger. The time complexity for this method is O(n^2).

Method 2 - Using BST property

You can verify this property by examining consecutive values in the preorder traversal and comparing each value to the last value in the list (acting as the maximum or minimum boundary).

Approach

  1. Compare Subsequent Nodes in Preorder Traversal:
    • Traverse the adjacency pairs of the preorder list.
    • For each pair of nodes preorder[i] and preorder[i+1], verify whether the value lies within the correct boundary (increasing or decreasing).
  2. Boundary Conditions:
    • During traversal, maintain the minimum and maximum range observed.
    • For non-leaf nodes, their only child will adjust the bounds accordingly.
  3. Output Determination:
    • If all pairs satisfy the conditions for a single child, return True.
    • Otherwise, return False.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

public class Solution {

    public boolean hasOnlyOneChild(int[] preorder) {
        int n = preorder.length;
        for (int i = 0; i < n - 1; i++) {
            int curr = preorder[i];
            int next = preorder[i + 1];
            int last = preorder[n - 1];

            // Check if curr and next are on the same side of "last"
            if ((next < curr && last < curr) || (next > curr && last > curr)) {
                continue;
            } else {
                return false; // Violation of single child property
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();

        int[] preorder1 = { 8, 3, 2, 6 };
        System.out.println(solution.hasOnlyOneChild(preorder1)); // Output: True

        int[] preorder2 = { 8, 3, 6, 2 };
        System.out.println(solution.hasOnlyOneChild(preorder2)); // Output: False
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution:
    def hasOnlyOneChild(self, preorder):
        n = len(preorder)
        for i in range(n - 1):
            curr = preorder[i]
            next_val = preorder[i + 1]
            last = preorder[-1]

            # Check if curr and next_val are on the same side of "last"
            if (next_val < curr and last < curr) or (next_val > curr and last > curr):
                continue
            else:
                return False  # Violation of single child property
        return True

# Example usage:
solution = Solution()

preorder1 = [8, 3, 2, 6]
print(solution.hasOnlyOneChild(preorder1))  # Output: True

preorder2 = [8, 3, 6, 2]
print(solution.hasOnlyOneChild(preorder2))  # Output: False

Complexity

  • ⏰ Time complexity: O(n), since the algorithm traverses the preorder array once.
  • 🧺 Space complexity: O(1). Only constant space is used for this comparison.