# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python 3 (ipykernel)
#     language: python
#     name: python3
# ---

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


# +
# Test the preorder traverse using tree in Example 2 [3,5,1,6,2,0,8,null,null,7,4]

#      3
#    /   \   
#   5     1  
#  / \   / \
# 6  2  0  8
#   / \
#  7  4

values = [3,5,1,6,2,0,8,None,None,7,4]
nodes = [TreeNode(x) for x in values if x != None]
root = nodes[0]

nodes[0].left, nodes[0].right = nodes[1], nodes[2]
nodes[1].left, nodes[1].right = nodes[3], nodes[4]
nodes[2].left, nodes[2].right = nodes[5], nodes[6]
nodes[4].left, nodes[4].right = nodes[7], nodes[8]


# +
# Preorder: Processes the root before the traversals of left and right children.

def traverse_tree_preorder(node, path=[]):
    if not node: return path
    path.append(node.val)  # or node
    if node.left:
        traverse_tree_preorder(node.left, path)
    if node.right:
        traverse_tree_preorder(node.right, path)
    return path


# -

traverse_tree_preorder(root)


# +
# find path to a node value
# refs: https://www.baeldung.com/cs/path-from-root-to-node-binary-tree

def find_path(root, value):
    def search(node, target):
        if not node:
            return False
        path.append(node.val)
        if node.val == target or search(node.left, target) or search(node.right, target):
            return True
        else:
            path.pop()
            return False

    path = []
    search(root, value)
    return path


# -

find_path(root, 4)



StarcoderdataJupyterScriptsDedupFiltered