Having Fun with BST #1

                   Binary Search Tree Problems(#1) 

A Binary Search Tree (BST) is a tree data structure that follows two properties

 1. Left sub-tree of a node has value less or equal to this  node's value.

 2.Right sub-tree of a node has value greater than or equal to this node's value.

With this two properties, BST is a powerful tool to store and retrieve data.  Here is some operations that support by BST and the time complexities.

  --   Search :  O(log N )

  --  Insert     :  O(log N )

  --  Delete    :  O(log N )

In order to search a target in BST, obviously, we need to traverse a BST.  Let's, then, see how we can traverse a BST.

Here are 3 general ways to traverse a BST:  

Pre - Order Traversal

In - Order Traversal

Post - Order Traversal  

We will walk through how to do them one by one, Besides, I would like to cover 2 other interesting way to do traverse.

Level - Order Traversal

ZigZag - Order Traversal

Ready ? Let's Roll !

Example Tree :

   

1. Pre - Order Traversal 

Basic idea of Pre - Order Traversal in pseudo code will be :
1. Visit the Current node.
2. Visit its Left Child
3. Visit  its Right Child

The result using this method to traverse the example tree above will be :
8 --> 3 --> 1 --> 6 --> 4 --> 7 --> 10 --> 14 --> 13.

Here is the recursive code for Pre-Order Traversal:


Here is the iterative code:




Notice that the sequence of stack push right child and then left child can not be change. 

 2. In-Order Traversal 

 This way in pseudo code will be:

1. Visit its Left Child.
2. Visit  the Current Node.
3. Visit  its Right Child

The result using this method to traverse the example tree above will be :
1 --> 3 --> 4 --> 6 --> 7 --> 8 --> 10 --> 13 --> 14

Notice that if a BST is valid the result of in-Order traversal is always sorted in increasing order. 

Recursive code:


Iterative code become Interesting :

3 . Post- Order Traversal

The pseudo code for post order will be:

1.Visit its Left Child
2.Visit its Right Child
3.Visit the Current Node
The result using this method to traverse the example tree above will be :
1 --> 4 --> 7 --> 6 --> 3 --> 13 --> 14 --> 10 --> 8

Recursive code will be:



Iterative way to do post-Order become easy when you have two stacks: 

4. Level-Order Traversal 

Yes! Just like the name. We gonna traverse our tree level by level. So here is the result sequence when we use level-Order traversal:
8 --> 3 --> 10 --> 1 --> 6 --> 14 --> 4 --> 7 --> 13

Here is a little quiz: What data structure you think gonna help us traverse tree this time ?

So, Previous we used stack a lot, but this time we gonna use a Queue, which actually make sense since it is like a BFS in a BST.

Here is how we gonna use a queue to do level-order traversal:

5. ZigZag - Order Traversal

Also like the name we will traverse the tree levelly by in ZigZag order !
Actually here is a question about this in LeetCode:

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]

Here is a solution using two stacks:



I think the code is very straightforward  and pretty much self-explained everything we want to do here.

Hope you had your favorite way to traverse a BST now :-)

Happy Coding^^
Ye Jiang