Traverse Binary Tree

#leetcode/techniques #algo/traverse

Tree traversal is the process of visiting each node in a tree data structure exactly once, in a particular order. There are two commonly used ways to traverse a tree:

data structure pros / cons
[[#Depth-First Traversal]] recursion stack might have stack overflow
DFS use own stack iteration stack prevent from stack overflow
[[#Breadth-First Traversal]] iteration queue

Depth-First Traversal

We first visit the left subtree recursively, then visit the right subtree recursively, and finally visit the root node.

Preorder traversal

    1
   / \
  2   3
 / \
4   5

output is 1 2 4 5 3

use system stack, recursion

void preorder(TreeNode *root) {
	if (root == nullptr) return;
	std::cout << root->val << std::endl;
	preorder(root->left);
	preorder(root->right);
}

use STL stack, iteration

void preorder(TreeNode* root) {
	stack<TreeNode*> st;
	if (root == nullptr) return;
	st.push(root);
	while (!st.empty()) {
		TreeNode* curr = st.top();
		st.pop();
		std::cout << curr->val << std::endl;
		if (curr->right != nullptr) st.push(curr->right);
		if (curr->left != nullptr) st.push(curr->left);
	}
}

Inorder Traversal

Visit the left subtree first, them visit the root node, and finally visit the right subtree. Thus the sequence in above tree will be:

    1
   / \
  2   3
 / \
4   5

output is 4 2 5 1 3

use system stack, recursion

void inorder(TreeNode *root) {
	if (root == nullptr) return;
	inorder(root->left);
	std::cout << root->val << std::endl;
	inorder(root->right);
}

use STL stack, iteration ⭐ hard

void inorder(TreeNode* root) {
	if (root == nullptr) return;
	stack<TreeNode*> st;
	TreeNode* curr = root;
	while (curr != nullptr || !st.empty()) {
		while (curr != nullptr) {
			st.push(curr);
			curr = curr->left;
		}
		curr = st.top()
		st.pop()
		std::cout << curr->val << std::endl;
		curr = curr->right;
	}
}

Postorder traversal

Visit the left node first, then visit the right node, and finally visit the root node. Thus the sequence in above tree will be:

    1
   / \
  2   3
 / \
4   5

output is 4 5 2 3 1

use system stack, recursion

void postorder(TreeNode *root) {
	if (root == nullptr) return;
	postorder(root->left);
	postorder(root->right);
	std::cout << root->val << std::endl;
}

use STL stack, iteration (TBD ⭐ Hard)

void postorder(TreeNode* root) {
	if (root == nullptr) return;
	stack<TreeNode*> st;
	TreeNode* prev = root;
	
}

Breadth-First Traversal

We visit nodes at the same level from left to right before moving down to the next level. Thus the sequence in above tree will be:

Use Queue

1, 2, 3, 4, 5, 6, 7

void bfsTraversal(Node* root) {
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        Node* current = q.front();
        q.pop();
        cout << current->val << " ";
        if (current->left != nullptr) {
            q.push(current->left);
        }
        if (current->right != nullptr) {
            q.push(current->right);
        }
    }
}