Skip to content

Latest commit

 

History

History
327 lines (258 loc) · 8.94 KB

Day 7 - Tree Boundary Traversal.md

File metadata and controls

327 lines (258 loc) · 8.94 KB
Difficulty Source Tags
Medium
160 Days of Problem Solving
Tree

🚀 Day 7. Tree Boundary Traversal 🧠

The problem can be found at the following link: Problem Link

💡 Problem Description:

Given a binary tree, the task is to return a list of nodes representing its boundary traversal in an anticlockwise direction, starting from the root. The boundary includes:

  1. The left boundary (excluding the leaf nodes).
  2. All the leaf nodes (both from left and right subtrees).
  3. The right boundary (excluding the leaf nodes), added in reverse order.

🔍 Example Walkthrough:

Example 1

Input:
root[] = [1, 2, 3, 4, 5, 6, 7, N, N, 8, 9, N, N, N, N]

Output:
[1, 2, 4, 8, 9, 6, 7, 3]

Explanation:

Example 2

Input:
root[] = [1, 2, N, 4, 9, 6, 5, N, 3, N, N, N, N 7, 8]

Output:
[1, 2, 4, 6, 5, 7, 8]

Explanation:

Example 3

Input:
root[] = [1, N, 2, N, 3, N, 4, N, N]

    1
     \
      2
       \
        3
         \
          4

Output:
[1, 4, 3, 2]

Explanation:

  • Left boundary: [1] (as there is no left subtree)
  • Leaf nodes: [4]
  • Right boundary: [3, 2] (in reverse order)
  • Final traversal: [1, 4, 3, 2]

Constraints

  • 1 <= Number of Nodes <= $10^4$
  • 1 <= Node Value <= $10^5$

🎯 My Approach:

The boundary traversal of a binary tree consists of three parts:

  1. Left Boundary:

    • Traverse the leftmost nodes, excluding the leaf nodes.
    • Move left whenever possible; otherwise, move right.

  2. Leaf Nodes:

    • Perform inorder traversal to collect leaf nodes.

  3. Right Boundary:

    • Traverse the rightmost nodes, excluding the leaf nodes.
    • Move right whenever possible; otherwise, move left.
    • Store nodes in a stack to reverse them before adding to the final result.

🕒 Time and Auxiliary Space Complexity

  • Time Complexity: O(N) Each node is visited at most once, so the time complexity is O(N).
  • Auxiliary Space Complexity: O(H) (Height of the tree) The recursion stack space in a skewed tree can be O(N). In a balanced tree, it will be O(log N).

📝 Solution Code

Code (C++)

class Solution {
    void lb(Node* r, vector<int>& v) {
        if (!r || (!r->left && !r->right)) return;
        v.push_back(r->data);
        lb(r->left ? r->left : r->right, v);
    }
    void rb(Node* r, vector<int>& v) {
        if (!r || (!r->left && !r->right)) return;
        rb(r->right ? r->right : r->left, v);
        v.push_back(r->data);
    }
    void leaf(Node* r, vector<int>& v) {
        if (!r) return;
        leaf(r->left, v);
        if (!r->left && !r->right) v.push_back(r->data);
        leaf(r->right, v);
    }
public:
    vector<int> boundaryTraversal(Node* r) {
        if (!r) return {};
        vector<int> v = {r->data};
        lb(r->left, v);
        leaf(r->left, v);
        leaf(r->right, v);
        rb(r->right, v);
        return v;
    }
};

🌲 Alternative Approaches

2️⃣ Iterative Approach Using Queue (BFS)

Algorithm

  • Traverse the left boundary iteratively.
  • Collect leaf nodes via BFS.
  • Traverse the right boundary iteratively in reverse order.
class Solution {
public:
    vector<int> boundaryTraversal(Node* root) {
        if (!root) return {};
        vector<int> res;
        if (root->left || root->right) res.push_back(root->data);
        
        Node* cur = root->left;
        while (cur) {
            if (cur->left || cur->right) res.push_back(cur->data);
            cur = cur->left ? cur->left : cur->right;
        }

        function<void(Node*)> leafNodes = [&](Node* node) {
            if (!node) return;
            leafNodes(node->left);
            if (!node->left && !node->right) res.push_back(node->data);
            leafNodes(node->right);
        };
        leafNodes(root);

        stack<int> rightBoundary;
        cur = root->right;
        while (cur) {
            if (cur->left || cur->right) rightBoundary.push(cur->data);
            cur = cur->right ? cur->right : cur->left;
        }

        while (!rightBoundary.empty()) {
            res.push_back(rightBoundary.top());
            rightBoundary.pop();
        }

        return res;
    }
};

3️⃣ Iterative DFS (Using Stack)

Algorithm

  • Use DFS traversal to visit nodes iteratively.
  • Push the left boundary.
  • Collect leaf nodes.
  • Push the right boundary in reverse.
class Solution {
public:
    vector<int> boundaryTraversal(Node* root) {
        if (!root) return {};
        vector<int> res;
        if (root->left || root->right) res.push_back(root->data);

        stack<Node*> s;
        Node* cur = root->left;
        while (cur) {
            if (cur->left || cur->right) res.push_back(cur->data);
            s.push(cur);
            cur = cur->left ? cur->left : cur->right;
        }

        function<void(Node*)> leafNodes = [&](Node* node) {
            if (!node) return;
            leafNodes(node->left);
            if (!node->left && !node->right) res.push_back(node->data);
            leafNodes(node->right);
        };
        leafNodes(root);

        stack<int> rightBoundary;
        cur = root->right;
        while (cur) {
            if (cur->left || cur->right) rightBoundary.push(cur->data);
            cur = cur->right ? cur->right : cur->left;
        }

        while (!rightBoundary.empty()) {
            res.push_back(rightBoundary.top());
            rightBoundary.pop();
        }

        return res;
    }
};

🔍 Comparison of Approaches

Approach Time Complexity Space Complexity Method Pros Cons
Recursive DFS 🟢 O(N) 🟡 O(H) Recursion Simple & structured Stack overflow for deep trees
Iterative BFS 🟢 O(N) 🔴 O(W) Queue-based Avoids recursion depth issues More memory for wide trees
Iterative DFS (Stack) 🟢 O(N) 🟡 O(H) Stack-based Explicit traversal order Extra space for stack

🚀 Best Choice?

  • For balanced trees, the Recursive DFS method is best.
  • For deep trees, the Iterative BFS is preferable.
  • For explicit iterative control, the DFS with Stack is an option.

Code (Java)

class Solution {
    void lb(Node r, ArrayList<Integer> v) {
        if(r==null || (r.left==null && r.right==null)) return;
        v.add(r.data);
        lb(r.left!=null ? r.left : r.right, v);
    }
    void rb(Node r, ArrayList<Integer> v) {
        if(r==null || (r.left==null && r.right==null)) return;
        rb(r.right!=null ? r.right : r.left, v);
        v.add(r.data);
    }
    void leaf(Node r, ArrayList<Integer> v) {
        if(r==null)return;
        leaf(r.left,v);
        if(r.left==null && r.right==null) v.add(r.data);
        leaf(r.right,v);
    }
    public ArrayList<Integer> boundaryTraversal(Node r) {
        ArrayList<Integer> v = new ArrayList<>();
        if(r==null)return v;
        v.add(r.data);
        lb(r.left, v);
        leaf(r.left, v);
        leaf(r.right, v);
        rb(r.right, v);
        return v;
    }
}

Code (Python)

class Solution:
    def boundaryTraversal(self, root):
        if not root:
            return []
        res = [root.data] if root.left or root.right else []

        cur = root.left
        while cur:
            if cur.left or cur.right:
                res.append(cur.data)
            cur = cur.left if cur.left else cur.right

        def leaf_nodes(node):
            if not node:
                return
            leaf_nodes(node.left)
            if not node.left and not node.right:
                res.append(node.data)
            leaf_nodes(node.right)

        leaf_nodes(root)

        right_boundary = []
        cur = root.right
        while cur:
            if cur.left or cur.right:
                right_boundary.append(cur.data)
            cur = cur.right if cur.right else cur.left

        res += reversed(right_boundary)
        return res

🎯 Contribution and Support:

For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: Any Questions. Let’s make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐

📍Visitor Count