Inorder traversal iterative solution for multiple questions for Leetcode BST problem

  • for tree inorder traversal, we have many different coding solution: recursion and iterative with stack mainly.

Iterative stack for basic inorder traversal

leetcode 94. Binary Tree Inorder Traversal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public List<Integer> inorderTraversal(TreeNode root){
	List<Integer> res = new ArrayList<>();
	if(root == null) return res;
	Stack<TreeNode> stack = new Stack<>();
	while(root != null || !stack.empty()){
		while(root != null){
			stack.push(root);
			root = root.left;
		}
		root = stack.pop();
		res.add(root.val);
		root = root.right;
	}
	return res;
}
  • Use this basic structure to find the kth smallest node
    Leetcode 230. Kth Smallest Element in a BST
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int KthSmallest(TreeNode root, int k){
	Stack<TreeNode> stack = new Stack<>();
	while(root != null || !stack.isEmpty()){
		//go all the way down to the left bottom if root is valid
		while(root != null){
			stack.push(root);
			root = root.left;
		}
		//pop the top and get the value and then go the left
		root = stack.pop();
		if(--k == 0) break;
		root = root.right;
	}
	return root.val;
}
Leetcode 98. Validate Binary Search Tree
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean isValidBST(TreeNode root){
	if(root == null) return true;
	Stack<TreeNode> stack = new Stack<>();
	TreeNode pre = null;
	while(root != null || !stack.empty()){
		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;
}