Created
November 19, 2013 21:03
-
-
Save rfaisal/7552550 to your computer and use it in GitHub Desktop.
It is easy to traverse a binary tree in-order using recursion. Do it without using recursion.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| public class TreeTraversal { | |
| public static void inOrderWithoutRecursion(TNode<Integer> parent){ | |
| TNode<Integer> current= parent; | |
| Stack<TNode<Integer>> stack =new Stack<TNode<Integer>>(); | |
| while(true){ | |
| if(current.left!=null){ | |
| stack.push(current); | |
| current=current.left; | |
| } | |
| else{ | |
| System.out.print(current.data); | |
| if(!stack.isEmpty()) | |
| current=stack.pop(); | |
| else | |
| break; | |
| System.out.print(current.data); | |
| current=current.right; | |
| } | |
| } | |
| } | |
| public static void inOrder(TNode<Integer> parent){ | |
| if(parent==null) | |
| return; | |
| inOrder(parent.left); | |
| System.out.print(parent.data); | |
| inOrder(parent.right); | |
| } | |
| public static void main(String[] args) { | |
| TNode<Integer> tree= new TNode<Integer>(1); | |
| tree.left=new TNode<Integer>(2); | |
| tree.right=new TNode<Integer>(3); | |
| tree.left.left=new TNode<Integer>(4); | |
| tree.left.right=new TNode<Integer>(5); | |
| tree.right.left=new TNode<Integer>(6); | |
| tree.right.right=new TNode<Integer>(7); | |
| tree.left.left.left=new TNode<Integer>(8); | |
| tree.left.left.right=new TNode<Integer>(9); | |
| tree.left.right.left=new TNode<Integer>(10); | |
| tree.left.right.right=new TNode<Integer>(11); | |
| tree.right.left.left=new TNode<Integer>(12); | |
| tree.right.left.right=new TNode<Integer>(13); | |
| tree.right.right.left=new TNode<Integer>(14); | |
| tree.right.right.right=new TNode<Integer>(15); | |
| inOrder(tree); | |
| System.out.println(""); | |
| inOrderWithoutRecursion(tree); | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment