Fading Coder

One Final Commit for the Last Sprint

Home > Notes > Content

Implementing Depth-First and Breadth-First Traversals for Binary Trees

Notes Oct 11 16

Depth-First Traversal (DFS)

LeetCode 144: Preorder Traversal

Recursive Approach:

class Solution {
public:
    void visitNodes(TreeNode* node, vector<int>& output) {
        if (!node) return;
        output.push_back(node->val);
        visitNodes(node->left, output);
        visitNodes(node->right, output);
    }

    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        visitNodes(root, result);
        return result;
    }
};

Iterative Approach:

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        if (!root) return result;
        
        stack<TreeNode*> nodeStack;
        nodeStack.push(root);
        
        while (!nodeStack.empty()) {
            TreeNode* current = nodeStack.top();
            nodeStack.pop();
            result.push_back(current->val);
            
            if (current->right) nodeStack.push(current->right);
            if (current->left) nodeStack.push(current->left);
        }
        return result;
    }
};

LeetCode 145: Postorder Traversal

Recursiev Approach:

class Solution {
public:
    void visitNodes(TreeNode* node, vector<int>& output) {
        if (!node) return;
        visitNodes(node->left, output);
        visitNodes(node->right, output);
        output.push_back(node->val);
    }

    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        visitNodes(root, result);
        return result;
    }
};

Iterative Appproach:

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        if (!root) return result;
        
        stack<TreeNode*> nodeStack;
        nodeStack.push(root);
        
        while (!nodeStack.empty()) {
            TreeNode* current = nodeStack.top();
            nodeStack.pop();
            result.push_back(current->val);
            
            if (current->left) nodeStack.push(current->left);
            if (current->right) nodeStack.push(current->right);
        }
        reverse(result.begin(), result.end());
        return result;
    }
};

LeetCode 94: Inorder Traversal

Recursive Appproach:

class Solution {
public:
    void visitNodes(TreeNode* node, vector<int>& output) {
        if (!node) return;
        visitNodes(node->left, output);
        output.push_back(node->val);
        visitNodes(node->right, output);
    }

    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        visitNodes(root, result);
        return result;
    }
};

Iterative Approach:

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> nodeStack;
        TreeNode* current = root;
        
        while (current || !nodeStack.empty()) {
            if (current) {
                nodeStack.push(current);
                current = current->left;
            } else {
                current = nodeStack.top();
                nodeStack.pop();
                result.push_back(current->val);
                current = current->right;
            }
        }
        return result;
    }
};

Breadth-First Traversal (BFS)

LeetCode 102: Level Order Traversal

Iterative Approach:

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> levels;
        queue<TreeNode*> visitQueue;
        
        if (root) visitQueue.push(root);
        
        while (!visitQueue.empty()) {
            int nodeCount = visitQueue.size();
            vector<int> currentLevel;
            
            for (int i = 0; i < nodeCount; ++i) {
                TreeNode* node = visitQueue.front();
                visitQueue.pop();
                currentLevel.push_back(node->val);
                
                if (node->left) visitQueue.push(node->left);
                if (node->right) visitQueue.push(node->right);
            }
            levels.push_back(currentLevel);
        }
        return levels;
    }
};

Recursive Approach:

class Solution {
public:
    void traverse(TreeNode* node, vector<vector<int>>& storage, int height) {
        if (!node) return;
        if (storage.size() <= height) storage.push_back({});
        storage[height].push_back(node->val);
        traverse(node->left, storage, height + 1);
        traverse(node->right, storage, height + 1);
    }

    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> storage;
        traverse(root, storage, 0);
        return storage;
    }
};

LeetCode 107: Bottom-Up Level Order Traversal

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> levels;
        queue<TreeNode*> visitQueue;
        
        if (root) visitQueue.push(root);
        
        while (!visitQueue.empty()) {
            int nodeCount = visitQueue.size();
            vector<int> currentLevel;
            
            for (int i = 0; i < nodeCount; ++i) {
                TreeNode* node = visitQueue.front();
                visitQueue.pop();
                currentLevel.push_back(node->val);
                
                if (node->left) visitQueue.push(node->left);
                if (node->right) visitQueue.push(node->right);
            }
            levels.push_back(currentLevel);
        }
        reverse(levels.begin(), levels.end());
        return levels;
    }
};

LeetCode 199: Binary Tree Right Side View

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> visibleNodes;
        queue<TreeNode*> visitQueue;
        
        if (root) visitQueue.push(root);
        
        while (!visitQueue.empty()) {
            int nodeCount = visitQueue.size();
            for (int i = 0; i < nodeCount; ++i) {
                TreeNode* node = visitQueue.front();
                visitQueue.pop();
                
                if (i == nodeCount - 1) visibleNodes.push_back(node->val);
                if (node->left) visitQueue.push(node->left);
                if (node->right) visitQueue.push(node->right);
            }
        }
        return visibleNodes;
    }
};

LeetCode 637: Average of Levels in Binary Tree

class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        vector<double> averages;
        queue<TreeNode*> visitQueue;
        
        if (root) visitQueue.push(root);
        
        while (!visitQueue.empty()) {
            int nodeCount = visitQueue.size();
            double sum = 0;
            
            for (int i = 0; i < nodeCount; ++i) {
                TreeNode* node = visitQueue.front();
                visitQueue.pop();
                sum += node->val;
                
                if (node->left) visitQueue.push(node->left);
                if (node->right) visitQueue.push(node->right);
            }
            averages.push_back(sum / nodeCount);
        }
        return averages;
    }
};

LeetCode 429: N-ary Tree Level Order Traversal

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        vector<vector<int>> levels;
        queue<Node*> visitQueue;
        
        if (root) visitQueue.push(root);
        
        while (!visitQueue.empty()) {
            int nodeCount = visitQueue.size();
            vector<int> currentLevel;
            
            for (int i = 0; i < nodeCount; ++i) {
                Node* node = visitQueue.front();
                visitQueue.pop();
                currentLevel.push_back(node->val);
                
                for (Node* child : node->children) {
                    if (child) visitQueue.push(child);
                }
            }
            levels.push_back(currentLevel);
        }
        return levels;
    }
};

LeetCode 515: Find Largest Value in Each Tree Row

class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        vector<int> maxValues;
        queue<TreeNode*> visitQueue;
        
        if (root) visitQueue.push(root);
        
        while (!visitQueue.empty()) {
            int nodeCount = visitQueue.size();
            int maxVal = INT_MIN;
            
            for (int i = 0; i < nodeCount; ++i) {
                TreeNode* node = visitQueue.front();
                visitQueue.pop();
                maxVal = max(maxVal, node->val);
                
                if (node->left) visitQueue.push(node->left);
                if (node->right) visitQueue.push(node->right);
            }
            maxValues.push_back(maxVal);
        }
        return maxValues;
    }
};

LeetCode 116 & 117: Populating Next Right Pointers

class Solution {
public:
    Node* connect(Node* root) {
        queue<Node*> visitQueue;
        if (root) visitQueue.push(root);
        
        while (!visitQueue.empty()) {
            int levelSize = visitQueue.size();
            Node* prev = nullptr;
            
            for (int i = 0; i < levelSize; ++i) {
                Node* current = visitQueue.front();
                visitQueue.pop();
                
                if (prev) prev->next = current;
                prev = current;
                
                if (current->left) visitQueue.push(current->left);
                if (current->right) visitQueue.push(current->right);
            }
            if (prev) prev->next = nullptr;
        }
        return root;
    }
};

LeetCode 104: Maximum Depth of Binary Tree

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (!root) return 0;
        
        queue<TreeNode*> visitQueue;
        visitQueue.push(root);
        int height = 0;
        
        while (!visitQueue.empty()) {
            int levelSize = visitQueue.size();
            height++;
            
            for (int i = 0; i < levelSize; ++i) {
                TreeNode* node = visitQueue.front();
                visitQueue.pop();
                
                if (node->left) visitQueue.push(node->left);
                if (node->right) visitQueue.push(node->right);
            }
        }
        return height;
    }
};

LeetCode 111: Minimum Depth of Binary Tree

class Solution {
public:
    int minDepth(TreeNode* root) {
        if (!root) return 0;
        
        queue<TreeNode*> visitQueue;
        visitQueue.push(root);
        int depth = 1;
        
        while (!visitQueue.empty()) {
            int levelSize = visitQueue.size();
            
            for (int i = 0; i < levelSize; ++i) {
                TreeNode* node = visitQueue.front();
                visitQueue.pop();
                
                if (!node->left && !node->right) return depth;
                if (node->left) visitQueue.push(node->left);
                if (node->right) visitQueue.push(node->right);
            }
            depth++;
        }
        return depth;
    }
};
Tags: Binary Treedepth-first search
Back to List

Prev: Converting Raster Data to Vector Boundaries with GDAL

Next: Open R1: A Comprehensive Evaluation vs GPT-4 and Claude 3

Related Articles

Designing Alertmanager Templates for Prometheus Notifications

How to craft Alertmanager templates to format alert messages, improving clarity and presentation. Alertmanager uses Go’s text/template engine with additional helper functions. Alerting rules referenc...

Deploying a Maven Web Application to Tomcat 9 Using the Tomcat Manager

Tomcat 9 does not provide a dedicated Maven plugin. The Tomcat Manager interface, however, is backward-compatible, so the Tomcat 7 Maven Plugin can be used to deploy to Tomcat 9. This guide shows two...

Skipping Errors in MySQL Asynchronous Replication

When a replica halts because the SQL thread encounters an error, you can resume replication by skipping the problematic event(s). Two common approaches are available. Methods to Skip Errors 1) Skip a...

Leave a Comment

Anonymous

◎Feel free to join the discussion and share your thoughts.

Copyright © fadingcoder.top