# Learn one iterative inorder traversal, apply it to multiple tree questions (Java Solution)

• I will show you all how to tackle various tree questions using iterative inorder traversal. First one is the standard iterative inorder traversal using stack. Hope everyone agrees with this solution.

Question : Binary Tree Inorder Traversal

``````public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root == null) return list;
Stack<TreeNode> stack = new Stack<>();
while(root != null || !stack.empty()){
while(root != null){
stack.push(root);
root = root.left;
}
root = stack.pop();
root = root.right;

}
return list;
}
``````

Now, we can use this structure to find the Kth smallest element in BST.

Question : Kth Smallest Element in a BST

`````` public int kthSmallest(TreeNode root, int k) {
Stack<TreeNode> stack = new Stack<>();
while(root != null || !stack.isEmpty()) {
while(root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
if(--k == 0) break;
root = root.right;
}
return root.val;
}
``````

We can also use this structure to solve BST validation question.

Question : Validate Binary Search Tree

``````public boolean isValidBST(TreeNode root) {
if (root == null) return true;
Stack<TreeNode> stack = new Stack<>();
TreeNode pre = null;
while (root != null || !stack.isEmpty()) {
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
if(pre != null && root.val <= pre.val) return false;
pre = root;
root = root.right;
}
return true;
}
``````

• Good summary

• good summary! thanks

• @issac3 Thank you so much :)

• good conclusion,thanks very much!

• it's really a good summary, lot's of thanks

• good summary

• i solve these problems just in the order of your summary!How funny

• Good summary and super helpful for iterative tree traversal question. This post deserves at least 200 upvotes.

• @issac3 That's a great summary, it would a great help if you could add iterative implementations of pre and post order traversals too. Thanks in advance!

• @issac3 very clean code and clear logic!! thanks.

• very nice summary!
Thanks a lot!

• @issac3 good summary

• pre

Concise and practical summary. Useful~ ~~

• Clean and simple. Very much helpful. Thank you so much :)

• Clean and good explanation

• Here is a python version of this algo:

``````class Solution(object):
#     An iterative solution
def isValidBST(self, root):
stack = []
pre = None
cur = root
while stack or cur:
while cur:
stack.append(cur)
cur = cur.left
top = stack.pop()
if pre is not None and pre.val >= top.val:
return False
pre = top
cur = top.right
return True
``````

• Nice code, easy to read and understand

• @issac3 Great job. Thanks.

The same solution can also be done in O(n) using if-else instead of the inner while

public boolean isValidBST(TreeNode root) {

``````    Stack<TreeNode> sTree = new Stack<>();

TreeNode curr = null;
TreeNode pre = null;
curr=root;

while(curr!=null || !sTree.isEmpty()){
if(curr!=null){
sTree.push(curr);
curr=curr.left;
}else{
curr=sTree.pop();
if(pre!=null && (pre.val>=curr.val)){
return false;
}
pre=curr;
curr=curr.right;
}
}
return true;
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.