Inorder Traversal of a BST

Oct 15

Visits nodes in ascending order

O(n)

	5
	/ \
	3 7
	/ \ \
	1 4 9
	# prints 1,3,4,5,7,9
	def inorder(root: TreeNode) -> None:
	if not root: return
	inorder(root.left)
	print(root.val)
	inorder(root.right)

view raw BSTInOrderTraversal.py hosted with ❤ by GitHub

	5
	/ \
	3 7
	/ \ \
	1 4 9
	// prints 1,3,4,5,7,9
	public void inorder(TreeNode root) {
	if (root == null) return;
	inorder(root.left);
	System.out.print(root.value + ",");
	inorder(root.right);
	}

view raw BSTInOrderTraversal.java hosted with ❤ by GitHub

A binary search tree is a binary tree where the left child is smaller and the right child is greater than its parent.
Traverse a BST using Inorder to:

· visit the tree in sorted order
· validate whether a binary tree is a binary search tree

LeetCode

98. Validate Binary Search Tree

Python | Java

	prev: TreeNode = None
	def isValidBST(self, root: Optional[TreeNode]) -> bool:
	if not root: return True
	if not self.isValidBST(root.left): return False
	if self.prev and self.prev.val >= root.val: return False
	self.prev = root
	return self.isValidBST(root.right)

view raw ValidateBinarySearchTree.py hosted with ❤ by GitHub

	TreeNode prev = null;
	public boolean isValidBST(TreeNode root) {
	if (root == null) return true;
	if (isValidBST(root.left) == false) return false;
	if (prev != null && prev.val >= root.val) return false;
	prev = root;
	return isValidBST(root.right);
	}