I can traverse the binary search tree using recursion easily, but I don't have an idea about traverse without recursion so please anyone explain,.....
2
-
1have you tried anything yourself at first. please post the codes where you are stuck.Mohammad Tauqir– Mohammad Tauqir2015-10-08 17:40:00 +00:00Commented Oct 8, 2015 at 17:40
-
1You should probably read Wikipedia page on Tree Traversal there are multiple algorithms there on how to do it with and without recursion.Edwin Dalorzo– Edwin Dalorzo2021-11-22 17:07:25 +00:00Commented Nov 22, 2021 at 17:07
Add a comment
|
1 Answer
yes, you can do it with stack. you have to take stack here the algorithm for p reorder, in-order and post-order traversal in iterative way (non recursive way/method) of binary search tree. Hope you will get properly.
p re order:
1) Create an empty stack node_Stack and push root node to stack.
2) Do following while node_Stack is not empty.
-> Pop an item from stack and print it.
-> Push right child of popped item to stack
-> Push left child of popped item to stack
in-order:
1) Create an empty stack S.
2) Initialize current node as root
3) Push the current node to S and set current = current->left until current is NULL
4) If current is NULL and stack is not empty then
-> Pop the top item from stack.
-> Print the popped item, set current = popped_item->right
-> Go to step 3.
5) If current is NULL and stack is empty then we are done.
post-order:
1.1 Create an empty stack
2.1 Do following while root is not NULL
-> Push root's right child and then root to stack.
-> Set root as root's left child.
2.2 Pop an item from stack and set it as root.
-> If the popped item has a right child and the right child
is at top of stack, then remove the right child from stack,
push the root back and set root as root's right child.
-> Else print root's data and set root as NULL.
2.3 Repeat steps 2.1 and 2.2 while stack is not empty.
Comments
