Coding - Preorder Traversal Without Invalid Nodes

Here is the full interview question "Coding - Preorder Traversal Without Invalid Nodes" asked at xAI:

Problem Statement

Given a binary tree where each node contains a value from 0 to 9, and the tree is rooted at node 0, find the preorder traversal of the tree containing only the nodes that have a value greater than 0.

A binary tree node is represented by a three-value tuple (node, left, right), where node is the value of the node, left is the left child node, and right is the right child node. If either left or right is None, then that child does not exist.

A preorder traversal visits the root node first, then traverses the left subtree, and finally traverses the right subtree.

Examples

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

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

Constraints

• The number of nodes in the tree is in the range [0, 10^4].
• 0 <= Node.val <= 9
• The tree is guaranteed to be a valid binary tree.

Hints

1. Use recursion to perform the preorder traversal.
2. Skip nodes with a value of 0.

Solution

To solve this problem, you can use a recursive approach to perform a preorder traversal of the binary tree. Here's a Python solution:

`python def traverse(root): if root is None: return []

result = []
if root[0] > 0:
    result.append(root[0])
result.extend(traverse(root[1]))
result.extend(traverse(root[2]))
return result

def preorderTraversal(root): return traverse(root) `

This solution defines a helper function traverse that recursively traverses the binary tree. If a node has a value greater than 0, it is added to the result list. The function then recursively traverses the left and right subtrees. The preorderTraversal function simply calls the traverse function with the root node.

Source: LeetCode Problem - Preorder Traversal Without Invalid Nodes