Coding - Boundary of Binary Tree

Here is the full interview question "Coding - Boundary of Binary Tree" asked at xAI:

---

Problem Statement

Given a binary tree, return the values of its boundary in anti-clockwise direction starting from root to leaf.

A binary tree is a tree data structure in which each node has at most two children, referred to as the left child and the right child.

Boundary nodes of a binary tree are the nodes which form the boundary of the tree including:

1. The root node.
2. All the leaf nodes.
3. All the nodes which have exactly one child, if there are no such nodes then consider only the leaf nodes.

The values of the nodes are located in the TreeNode.val.

Example:

1 / \ 2 3 / \ 4 5

The boundary of this tree is [1, 2, 4, 5, 3].

Constraints

• The number of nodes in the binary tree will be in the range [1, 50000].
• 0 <= Node.val <= 10^6

Examples

1. Input: root = [1,2,3,null,4,5] Output: [1,2,4,5,3]

2. Input: root = [1,null,2,3,null,4,null,null,5] Output: [1,2,3,4,5]

Hints

1. Use a depth-first search (DFS) approach to traverse the tree.
2. Keep track of the left boundary, right boundary, and leaf nodes separately.
3. Combine the results in the correct order.

Solution

To solve this problem, you can use a depth-first search (DFS) approach to traverse the tree and keep track of the left boundary, right boundary, and leaf nodes separately. Here's a Python solution using DFS:

`python class Solution: def boundaryOfBinaryTree(self, root: TreeNode) -> List[int]: if not root: return []

    res = []
    if root.left is None and root.right is None:
        return [root.val]
    
    # Left boundary
    self.dfsLeft(root.left, res)
    res.append(root.val)
    
    # Right boundary
    self.dfsRight(root.right, res)
    
    # Leaf nodes
    self.dfsLeaves(root.left, res)
    self.dfsLeaves(root.right, res)
    
    return res

def dfsLeft(self, node, res):
    if not node:
        return
    if not node.left and not node.right:
        res.append(node.val)
        return
    res.append(node.val)
    self.dfsLeft(node.left, res)

def dfsRight(self, node, res):
    if not node:
        return
    if not node.left and not node.right:
        res.append(node.val)
        return
    res.append(node.val)
    self.dfsRight(node.right, res)

def dfsLeaves(self, node, res):
    if not node:
        return
    if not node.left and not node.right:
        res.append(node.val)
        return
    self.dfsLeaves(node.left, res)
    self.dfsLeaves(node.right, res)

`

This solution uses three helper functions: dfsLeft, dfsRight, and dfsLeaves to traverse the left boundary, right boundary, and leaf nodes, respectively. The results are combined in the correct order to form the boundary of the binary tree.

---

I hope this helps! Let me know if you have any questions.