Binary Search Tree - Iterative inorder tree walk

Today, I’ll walk you through an iterative algorithm for inorder tree walk over a Binary search tree. First, let me draw your attention to an exercise in the CLRS book [1].

Exercise 12.1-3

Give a nonrecursive algorithm that performs an inorder tree walk. (Hint: An easy solution uses a stack as an auxiliary data structure. A more complicated, but elegant, solution uses no stack but assumes that we can test two pointers for equality.)

The one which uses a stack is relatively simple. Here’s how it looks.

**Input:** $root$ node of the tree $T$  
$INORDER-TREEWALK-ITERATIVE(root)$  
$\phantom{{}++{}}$ Let $s$ be an empty stack  
$\phantom{{}++{}}$ TreeNode $\;\;current \gets root$  
$\phantom{{}++{}}$  `while`$\;!s.isEmpty$ or $current \;\neq sentinel$  
$\phantom{{}++{}}$  $\phantom{{}++{}}$ `if` $current \neq sentinel$  
$\phantom{{}++{}}$  $\phantom{{}++{}}$ $\phantom{{}++{}}$  $s.push(current)$  
$\phantom{{}++{}}$  $\phantom{{}++{}}$ $\phantom{{}++{}}$ $current \gets current.left$  
$\phantom{{}++{}}$  $\phantom{{}++{}}$ `else`  
$\phantom{{}++{}}$  $\phantom{{}++{}}$ $\phantom{{}++{}}$  TreeNode $\;r \gets s.pop()$  
$\phantom{{}++{}}$  $\phantom{{}++{}}$ $\phantom{{}++{}}$ print $r$  
$\phantom{{}++{}}$  $\phantom{{}++{}}$ $\phantom{{}++{}}$ $current \gets r.right$


Now let’s go ahead and write an iterator that performs an inorder tree walk on our BST.

Implement the BSTIterator class that represents an iterator over the in-order traversal of a binary search tree (BST):

  • BSTIterator(TreeNode root) Initializes an object of the BSTIterator class. The root of the BST is given as part of the constructor. The pointer should be initialized to a non-existent number smaller than any element in the BST.
  • boolean hasNext() Returns true if there exists a number in the traversal to the right of the pointer, otherwise returns false.
  • int next() Moves the pointer to the right, then returns the number at the pointer.

Notice that by initializing the pointer to a non-existent smallest number, the first call to next() will return the smallest element in the BST.

You may assume that next() calls will always be valid. That is, there will be at least a next number in the in-order traversal when next() is called. 

Example 1:

 
 
 
 

By using the algorithm defined above, let’s implement the iterator.



Analysis

Each hasNext() call takes $Θ(1)$. We access each node of the BST twice, pushing it onto the stack, and later, popping it off the stack. Therefore, our next() call takes only $Θ(1)$ time. We use a stack data structure with height $h + 1$ for storing the nodes during the traversal where $h$ is the height of the tree. Thus, our algorithm uses  $Θ(h)$ memory. 

References

[1] https://www.amazon.com/Introduction-Algorithms-3rd-MIT-Press/dp/0262033844

Comments

Post a Comment

Popular posts from this blog

Introducing Java Reactive Extentions in to a SpringBoot Micro Service

Image
Introduction Today we are going to take a look at Reactive Programming using Java8 and RxJava, which is a library for composing asynchronous and event-based programs by using observable sequences. RxJava stands for Reactive Extensions for the JVM. It extends the observer pattern [Gamma95] to support sequences of data/events and adds operators that allow you to compose sequences together declaratively while abstracting away concerns about things like low-level threading, synchronization, thread-safety and concurrent data structures [1]. Pre-Requisites : Having a good knowledge about Java8, Functional Programming and spring boot microservices. What is Reactive programming? In essence, Reactive programming is an asynchronous programming paradigm concerned with data streams. The system time, a list of entries from the DB/API, user clicks, everything can be a stream of data. Data from different streams can easily be combined and transformed, and in the end processed/observed by the
Read more

Optimal binary search trees

Image
Suppose that we are designing a program to translate text from English to French. For each occurrence of each English word in the text, we need to look up its French equivalent. We could perform these lookup operations by building a binary search tree with $n$ English words as keys and their French equivalents as satellite data. Because we will search the tree for each individual word in the text, we want the total time spent searching to be as low as possible. We could ensure an $Θ(log_2 \;n)$ search time per occurrence by using a red-black tree or any other balanced binary search tree. Words appear with different frequencies, however, and a frequently used word such as the may appear far from the root while a rarely used word appears near the root. Such an organization would slow down the translation, since the number of nodes visited when searching for a key in a binary search tree equals one plus the depth of the node containing the key. We want words that occur frequently in the t
Read more

Combining the emissions of multiple Observables together using RxJava Zip operator in a Spring Boot Micro service

Image
Introduction Well, today we are going to discuss an advanced RxJava operator called Zip. Let’s first take a look at the zip operator at a glance and then move on to a real world example that leverages the capabilities of the operator. In fact, zip is a very powerful and useful operator provided in the RxJava library. Prerequisites : Good knowledge of Java8, Functional Programming, RxJava, Spring Boot, Microservices. User Level : Advanced Since this is an advanced article, I am not going to walk you through the basics of RxJava or Spring Boot microservices. If you need to get some basic understanding of RxJava, I thoroughly recommend you to go through one of my previous blog posts [1] [2] or any other good introductory article about RxJava. If you need to learn more about Spring Boot microservices please go through some of the spring tutorials which are really comprehensive and impressive. RxJava Zip Operator Combines the emissions of multiple Observables together via a speci
Read more