Check if each internal node of a BST has exactly one child

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

Examples
Input: pre[] = {22, 12, 14, 17, 12}
Output: Yes

A Binary Search Tree (BST) is a tree in which all the nodes follow the below-mentioned properties −

  • The left sub-tree of a node has a key less than or equal to its parent node’s key.
  • The right sub-tree of a node has a key greater than to its parent node’s key.greater than to its parent node’s key.

The given array represents following BST. In the following BST, every internal
node has exactly 1 child. Therefore, the output is true.
22
/
12
\
14
\
17
/
11

In Preorder traversal, descendants (or Preorder successors) of every node appear after the node.  In this traversal method, the root node is visited first, then the left subtree and finally the right subtree.

In order to say, if all internal nodes have only one child in a BST, then all the descendants of every node are either smaller or larger than the node.  Since the tree is BST and every node has only one child, all descendants of a node will either be on the left side or right side means all descendants will either be smaller or greater.

Algorithm: All the descendants must either be larger or smaller than the node.

1. Find the next preorder successor of the node.
2. Find the last preorder successor (last element in pre[]) of the node.
3. a) If both successors are less than the current node, or both successors are greater than           the current node, then continue.
b) Else, return false.

Following java program implements the above algorithm:

 

 

LEAVE A REPLY