Decide if a Binary Tree is Binary Search Tree

Question:
Given a binary tree, validate if it's a binary search tree.

Analysis:
The elements in a BST are sorted if traversed in-order. This is a very important feature BST and based on the definition, the problem can be solved by in-order traversal.

The class definition of tree node:

Based on the analysis above, we can have the implementation below.

Many people may think we can simply check "left.value < parent.value < right.value" for each node. That being said, we can have an implementation like this:

However, this is not correct. Simply checking the parent and children relationship is not sufficient. Here is a counter-example.

      5
     /  \
    /    \
   3    7
  / \    / \
2  6  4  9

This is a top-down approach although it's not correct. If adding more constraints on the value for each node, there is a working solution for this. Here is the implementation:

Binary Tree Comparison

Problem:
Given two binary trees, compare if they are the same. If yes, return true, otherwise return false.

Analysis:
This is a very common programming interview question. Not that hard but it's very good to test the idea of recursion. Also, there are some edge cases one needs to consider.

Complexity:
Since it's a binary tree, should consider average case and worst case.
Balanced or unbalanced?

Solution:

Lowest Common Ancestor in Binary Search Tree Given Two Values

Problem:
Given a Binary Search Tree (BST) and two values, find the lowest common ancestor.

Note:
Two values are given in this problem, instead of two nodes. But the idea should be similar. Here I am giving two options: one is to find the node first and then search by node, and the other is to directly search by value. However, these two are the same in nature: comparing by value and validating the nodes.

Assumption:
The values are distinct in the BST. If not, the problem will become complicated. Consider the BST with all equal values in nodes.

Complexity:
Average case? Worst case?
For BST, balanced or unbalanced? Need to take this into consideration.

Solution 1:
Find the nodes first and then search by node.


Solution 2:
Directly search by value and then validate the values.

Nonrecursive Algorithm to Inorder Traverse Binary Tree

In previous post, I discussed the nonrecursive algorithm with stack to inorder traverse a binary tree. That's also pretty straightforward. In fact, we can implement the inorder traversal of binary trees without stack. This is more complicated but elegant.

For this approach, I use one more pointer to record the subtree already visited. Also, we need keep in mind that we are doing INORDER traversal. Therefore, if the right subtree of a node has been visited, the node itself must have been visited.


Related Posts:

Nonrecursive Algorithm with Stack to Inorder Traverse Binary Tree

Nonrecursive Algorithm to Inorder Traverse Binary Tree

The recursive algorithm is simple and straightforward. Now I am discussing the nonrecursive version. One solution is to use an auxiliary stack, with time and space both \(O(n)\) in worst case.



The above code can be modified a little bit as shown below. These 2 versions will work exactly the same.


Related Posts:

Nonrecursive Algorithm without Stack to Inorder Traverse Binary Tree

Structure of Tree Node

Background:

If each node of an arbitrary tree contains 3 pointer fields: left-child, right-sibling, and parent, from any node in the tree, its parent can be reached and identified in constant time and all its children can be reached and identified in time linear in the number of children.

Question:

How to use only 2 pointers and 1 boolean value in each node so that the parent of a node or all of its children can be reached in time linear in the number of children.

(Source: CLRS, Introduction to Algorithms, 2nd Edition, Page 217, Problem 10.4-6)

Answer:

Use 2 pointers left and right, where left always points to its leftmost child or NIL for leaves, and right generally points to right sibling but for rightmost node it points back to the parent. Then the boolean variable should record whether the node is rightmost or not. In this way, each parent node and its children form a loop in the tree (parent's left pointer and all children's right pointer), and they can be reached in time linear in the number of children.