http://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion/
http://leetcode.com/2010/04/binary-search-tree-in-order-traversal.html
Given a binary tree, return the in-order traversal of its nodes' values
The last traversed node must not have a right child.
Why this is true? To prove this, we assume the opposite, that is: the last traversed node has a right child. This is certainly incorrect, as in-order traversal would have to traverse its right child next before the traversal is done. Since this is incorrect, the last traversed node must not have a right child by contradiction.
First, the current pointer is initialized to the root. Keep traversing to its left child while pushing visited nodes onto the stack. When you reach a NULL node (ie, you’ve reached a leaf node), you would pop off an element from the stack and set it to current. Now is the time to print current’s value. Then, current is set to its right child and repeat the process again. When the stack is empty, this means you’re done printing.
To solve this issue, we need to develop an iterative solution. The idea is easy, we need a stack to store previous nodes, and a visited flag for each node is needed to record if the node has been visited before. When a node is traversed for the second time, its value will be printed. After its value is printed, we push its right child and continue from there.
Morris Traversal
We can take advantage of the empty right child of in-order predecessor of current node.
From http://www.cnblogs.com/TenosDoIt/p/3445449.html
Recursive
http://leetcode.com/2010/04/binary-search-tree-in-order-traversal.html
By adding a parent pointer to the data structure, this allows us to return to a node’s parent (Credits to my friend who provided this solution to me). To determine when to print a node’s value, we would have to determine when it’s returned from. If it’s returned from its left child, then you would print its value then traverse to its right child, on the other hand if it’s returned from its right child, you would traverse up one level to its parent.
By using a Threaded Binary Tree.
http://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion-and-without-stack/
Read full article from LeetCode - Binary Tree Inorder Traversal | Darren's Blog
http://leetcode.com/2010/04/binary-search-tree-in-order-traversal.html
Given a binary tree, return the in-order traversal of its nodes' values
The last traversed node must not have a right child.
Why this is true? To prove this, we assume the opposite, that is: the last traversed node has a right child. This is certainly incorrect, as in-order traversal would have to traverse its right child next before the traversal is done. Since this is incorrect, the last traversed node must not have a right child by contradiction.
void in_order_traversal_iterative(BinaryTree *root) {
stack<BinaryTree*> s;
BinaryTree *current = root;
while (!s.empty() || current) {
if (current) {
s.push(current);
current = current->left;
} else {
current = s.top();
s.pop();
cout << current->data << " ";
current = current->right;
}
}
}
Iterative: Using Stack-Time: O(n), Space: O(logn)First, the current pointer is initialized to the root. Keep traversing to its left child while pushing visited nodes onto the stack. When you reach a NULL node (ie, you’ve reached a leaf node), you would pop off an element from the stack and set it to current. Now is the time to print current’s value. Then, current is set to its right child and repeat the process again. When the stack is empty, this means you’re done printing.
void inOrder(struct tNode *root){ /* set current to root of binary tree */ struct tNode *current = root; struct sNode *s = NULL; /* Initialize stack s */ bool done = 0; while (!done) { /* Reach the left most tNode of the current tNode */ if(current != NULL) { /* place pointer to a tree node on the stack before traversing the node's left subtree */ push(&s, current); current = current->left; } /* backtrack from the empty subtree and visit the tNode at the top of the stack; however, if the stack is empty, you are done */ else { if (!isEmpty(s)) { current = pop(&s); printf("%d ", current->data); /* we have visited the node and its left subtree. Now, it's right subtree's turn */ current = current->right; } else done = 1; } } /* end of while */ }
public ArrayList<Integer> inorderTraversal(TreeNode root) {
ArrayList<Integer> result = new ArrayList<Integer>();
if (root == null)
return result;
Deque<TreeNode> stack = new ArrayDeque<TreeNode>(); // Used to restore parents
TreeNode p = root;
while (p != null || !stack.isEmpty()) {
if (p != null) { // Whenever we meet a node, push it into the stack and go to its left subtree
stack.push(p);
p = p.left;
} else { // Left subtree has been traversed, add the value of current node, and go to its right subtree
p = stack.pop();
result.add(p.val);
p = p.right;
}
}
return result;
}
ArrayList<Integer> ret = new ArrayList<Integer>();
if(root == null){
return ret;
}
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode cur = root;
while(true){
while(cur != null){
stack.push(cur);
cur = cur.left;
}
if(stack.isEmpty()){
break;
}
cur = stack.pop();
ret.add(cur.val);
cur = cur.right;
}
return ret;
}
Push first: http://rleetcode.blogspot.com/2014/09/binary-tree-inorder-traversal-java.htmlpublic List<Integer> inorderTraversal(TreeNode root) {ArrayList<Integer> result= new ArrayList<Integer>();if (root == null){return result;}Stack<TreeNode> stack = new Stack<TreeNode> ();// extract as a method pushAllLeft(root)while (root!=null){stack.push(root);root=root.left;}while(!stack.isEmpty()){TreeNode current = stack.pop();result.add(current.val);if (current.right != null){root=current.right;while(root!=null){stack.push(root);root=root.left;}}}return result;}http://gongxuns.blogspot.com/2012/12/leetcodebinary-tree-inorder-traversal.html
http://leetcode.com/2010/04/binary-search-tree-in-order-traversal.htmlpublic ArrayList<Integer> inorderTraversal(TreeNode root) { ArrayList<Integer> res = new ArrayList<Integer>(); if(root==null) return res; Stack<TreeNode> s = new Stack<TreeNode>(); TreeNode cur = root; while(!s.isEmpty()||cur!=null){ if(cur!=null){ s.push(cur); cur=cur.left; }else{ cur=s.pop(); res.add(cur.val); cur=cur.right; } } return res; }
To solve this issue, we need to develop an iterative solution. The idea is easy, we need a stack to store previous nodes, and a visited flag for each node is needed to record if the node has been visited before. When a node is traversed for the second time, its value will be printed. After its value is printed, we push its right child and continue from there.
void in_order_traversal_iterative(BinaryTree *root) {
stack<BinaryTree*> s;
s.push(root);
while (!s.empty()) {
BinaryTree *top = s.top();
if (top != NULL) {
if (!top->visited) {
s.push(top->left);
} else {
cout << top->data << " ";
s.pop();
s.push(top->right);
}
} else {
s.pop();
if (!s.empty())
s.top()->visited = true;
}
}
}
Alternative Solution:
void in_order_traversal_iterative(BinaryTree *root) {
stack<BinaryTree*> s;
BinaryTree *current = root;
bool done = false;
while (!done) {
if (current) {
s.push(current);
current = current->left;
} else {
if (s.empty()) {
done = true;
} else {
current = s.top();
s.pop();
cout << current->data << " ";
current = current->right;
}
}
}
}
We can even do better by refactoring the above code. The refactoring relies on one important observation:Morris Traversal
We can take advantage of the empty right child of in-order predecessor of current node.
From http://www.cnblogs.com/TenosDoIt/p/3445449.html
关于Morris Traversal算法，他是基于线索二叉树，它利用二叉树节点中闲置的右指针指向该节点在中序序列中的后缀节点。该算法的空间复杂度为O(1)
文中给出算法步骤如下：
1. Initialize current as root
2. While current is not NULL
If current does not have left child
a) Print current’s data
b) Go to the right, i.e., current = current->right
Else
a) Make current as right child of the rightmost node in current's left subtree
b) Go to this left child, i.e., current = current->left
重复以下1、2直到当前节点为空。
1. 如果当前节点的左孩子为空，则输出当前节点并将其右孩子作为当前节点。
2. 如果当前节点的左孩子不为空，在当前节点的左子树中找到当前节点在中序遍历下的前驱节点（即当前节点的左子树的最右节点）。
a) 如果前驱节点的右孩子为空，将它的右孩子设置为当前节点（利用这个空的右孩子指向它的后缀）。当前节点更新为当前节点的左孩子。
b) 如果前驱节点的右孩子为当前节点，将它的右孩子重新设为空（恢复树的形状）。输出当前节点。当前节点更新为当前节点的右孩子。
public ArrayList<Integer> inorderTraversal(TreeNode root) {
ArrayList<Integer> result = new ArrayList<Integer>();
TreeNode p = root, q = null;
while (p != null) {
if (p.left == null) { // Empty left subtree
result.add(p.val);
p = p.right;
} else {
// Find in-order predecessor of current node
q = p.left;
while (q.right != null && q.right != p)
q = q.right;
if (q.right == null) { // Its left subtree has not been traversed; link it to its predecessor
q.right = p;
p = p.left;
} else { // Its left subtree has been traversed; recover tree structure
q.right = null;
result.add(p.val);
p = p.right;
}
}
}
return result;
}
Recursive
public ArrayList<Integer> inorderTraversal(TreeNode root) {
ArrayList<Integer> result = new ArrayList<Integer>();
recursiveInorderTraversal(root, result);
return result;
}
private void recursiveInorderTraversal(TreeNode root, ArrayList<Integer> result) {
if (root == null)
return;
recursiveInorderTraversal(root.left, result);
result.add(root.val);
recursiveInorderTraversal(root.right, result);
}
Is it possible to do in-order traversal without a stack?http://leetcode.com/2010/04/binary-search-tree-in-order-traversal.html
By adding a parent pointer to the data structure, this allows us to return to a node’s parent (Credits to my friend who provided this solution to me). To determine when to print a node’s value, we would have to determine when it’s returned from. If it’s returned from its left child, then you would print its value then traverse to its right child, on the other hand if it’s returned from its right child, you would traverse up one level to its parent.
By using a Threaded Binary Tree.
Implement an inorder traversal with O(1) space - when node has parent node InorderTraversalWithParentTemplate.java
public static <T> void inOrderTraversal(BinaryTree<T> r) {
// Empty tree.
if (r == null) {
return;
}
BinaryTree<T> prev = null, curr = r, next;
while (curr != null) {
if (prev == null || prev.getLeft() == curr || prev.getRight() == curr) {
if (curr.getLeft() != null) {
next = curr.getLeft();
} else {
System.out.println(curr.getData());
next = (curr.getRight() != null ? curr.getRight() : curr.getParent());
}
} else if (curr.getLeft() == prev) {
System.out.println(curr.getData());
next = (curr.getRight() != null ? curr.getRight() : curr.getParent());
} else {
next = curr.getParent();
}
prev = curr;
curr = next;
}
}
