Binary tree

Solution:
We know how to represent an Linked List programatically. This is not much of an difference from that..
In Linked List, each node consists of an 2 variables named val & next.
In case of Binary Tree, each node consists of 3 variables named val, left & right.

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
a = Node("a")
b = Node("b")
c = Node("c")
d = Node("d")
e = Node("e")
f = Node("f")

a.left = b
a.right = c
b.left = d
b.right = e
c.right = f

#          a
#       /    \
#      b      c
#    /  \      \
#   d   e       f

Problem:
Write a function, depth_first_values, that takes in the root of a binary tree.
The function should return a list containing all values of the tree in depth-first order.

Solution:
What is Depth First Traversal?
— Let’s see how the depth first travel will be in case of above binary tree.
— Will start the traversal of tree, with root node.
— Then which ever path we take from root node, that needs to be traversed as depth as possible, before traversing lateral movement.
— In the above case; it will be: a → b → d → e → c → f
— In order to traverse an binary tree in depth first manner, the data structure needed is Stack
Stack data structure:
— Stack data structure is used for traversing the Binary Tree in depth first order. So, we need to know how Stack data structure works.

— Stack is the name given to an data structure which behaves in above way.
Coming to python, stack data structure is list & this is how above picture can be turned into code.
— The last element you push into stack will be the one coming out, when you want to pop an element from stack.

my_stack = []
my_stack.append(1)  # 1
my_stack.append(2)  # 1, 2
my_stack.append(3)  # 1, 2, 3
my_stack.pop()      # 3

Recursive approach:

— We already know that any recrusive problem is composed of two steps. base case & recursive step.
— Leap of faith concept needs to be understood before we write the recursive step.
When we make recursive calls, it’s as if we are taking recursive leap of faith(We will assume that when we make recursive all on the child,
we will get back the result that we are supposed to get).
— Once we get the result from left child tree & right child tree, we have to think how to frame the final result & return.
This is how return [ root.val, *left_values, *right_values ], in this case.

def depth_first_values(root):
    # Base case.
    if not root:
        return []

    # Recursive step
    left_values = depth_first_values(root.left)
    right_values = depth_first_values(root.right)
    return [root.val, *left_values, *right_values]

Iterative approach:

def depth_first_values(root):
    # This is just an edge case.
    # If the root node is empty, which means if the tree ifself is empty,
    # Then, the result is [].
    if not root:
        return []

    # We have to start the traversal from root of the tree.
    # Hence, i am inserting root Node into the stack.
    stack = [root]
    values = []

    # All iterative approaches will usually has the while loop.

    # Inside while loop, this is the repeated work will be doing.
    # Will pop out an node & treat it as curr_node.
    # We can do whatever work on that curr_node needs to be done,
    # as per the problem.
    # In this case, we are just appending the curr_node to the list.
    # Then, will append the childs of the curr_node to list,
    # after checking if those nodes are present.

    # At the end of the loop, just return the values.
    while stack:
        curr_node = stack.pop()
        values.append(curr_node.val)
        if curr_node.right:
            stack.append(curr_node.right)
        if curr_node.left:
            stack.append(curr_node.left)
    return values

Problem:
Write a function, breadth_first_values, that takes in the root of a binary tree.
The function should return a list containing all values of the tree in breadth-first order.

Solution:
What is Breadth First Traversal?
— Like the name indicates, it’s traversal of the tree in breadth manner. a → b → c → d → e → f
— In order to traverse an binary tree in breadth first manner, the data structure needed is queue
Queue data structure
— Queue data structure is used for traversing the Binary Tree in breadth first order. So, we need to know how Queue data structure works.
— Think about the queue data structure working analogous to people standing in the grocery queue line.

— Queue is the name given to an data structure which behaves in above way. Coming to python, queue data structure is list & this is how above picture can be turned into code.
— The first element you push into queue will be the one coming out, when you want to pop an element from queue.

my_queue = []
my_queue.append(1)  # 1
my_queue.append(2)  # 1, 2
my_queue.append(3)  # 1, 2, 3
my_queue.pop(0)     # 1

Recursive approach:

Only works in cool way in case of Depth first search 🙂

Iterative approach:

def breadth_first_values(root):
    if root is None:
        return []
    queue = [root]
    result = []
    while queue:
        curr_node = queue.pop(0)
        result.append(curr_node.val)
        if curr_node.left:
            queue.append(curr_node.left)
        if curr_node.right:
            queue.append(curr_node.right)
    return result

Problem:
Write a function, tree_sum, that takes in the root of a binary tree that contains number values.
The function should return the total sum of all values in the tree.

# test_00
a = Node(3)
b = Node(11)
c = Node(4)
d = Node(4)
e = Node(-2)
f = Node(1)

a.left = b
a.right = c
b.left = d
b.right = e
c.right = f

#       3
#    /    \
#   11     4
#  / \      \
# 4   -2     1

tree_sum(a) # -> 21

Solution:

Depth first search — Recursive approach:

def tree_sum(root):
    if root is None:
        return 0
    return root.val + tree_sum(root.left) + tree_sum(root.right)

Breadth first search — Iterative approach:

from collections import deque

def tree_sum(root):
    if not root:
        return 0
    queue = deque([root])
    total_sum = 0
    while queue:
        node = queue.popleft()
        total_sum += node.val
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    return total_sum

Problem:
Write a function, tree_includes, that takes in the root of a binary tree and a target value. The function should return a boolean indicating whether or not the value is contained in the tree.

# test_00
a = Node("a")
b = Node("b")
c = Node("c")
d = Node("d")
e = Node("e")
f = Node("f")

a.left = b
a.right = c
b.left = d
b.right = e
c.right = f

#      a
#    /   \
#   b     c
#  / \     \
# d   e     f

tree_includes(a, "e") # -> True

Solution:

Depth first search — Recursive approach:

def tree_includes(root, target):
    if not root:
        return False

    if root.val == target:
        return True

    return tree_includes(root.left, target) or tree_includes(root.right, target)

Breadth first search — Iterative approach:

from collections import deque

def tree_includes(root, target):
    if not root:
        return False
    queue = deque([root])
    while queue:
        node = queue.popleft()
        if node.val == target:
            return True
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    return False

Problem:
Write a function, tree_min_value, that takes in the root of a binary tree that contains number values. The function should return the minimum value within the tree. You may assume that the input tree is non-empty.

# test_00
a = Node(3)
b = Node(11)
c = Node(4)
d = Node(4)
e = Node(-2)
f = Node(1)

a.left = b
a.right = c
b.left = d
b.right = e
c.right = f

#       3
#    /    \
#   11     4
#  / \      \
# 4   -2     1
tree_min_value(a) # -> -2

Solution:

Depth first search — Recursive approach:

def tree_min_value(root):
    if root is None:
        return float("inf")

    smallest_left_value = tree_min_value(root.left)
    smallest_right_value = tree_min_value(root.right)
    return min(root.val, smallest_left_value, smallest_right_value)

Breadth first search — Iterative approach:

def tree_min_value(root):
    queue = [root]
    smallest = float("inf")
    while queue:
        current = queue.pop(0)
        if current.val < smallest:
            smallest = current.val
        if current.left is not None:
            queue.append(current.left)
        if current.right is not None:
            queue.append(current.right)
    return smallest

Problem:
Write a function, max_path_sum, that takes in the root of a binary tree that contains number values. The function should return the maximum sum of any root to leaf path within the tree.
You may assume that the input tree is non-empty.

# test_00
a = Node(3)
b = Node(11)
c = Node(4)
d = Node(4)
e = Node(-2)
f = Node(1)

a.left = b
a.right = c
b.left = d
b.right = e
c.right = f

#       3
#    /    \
#   11     4
#  / \      \
# 4   -2     1

max_path_sum(a) # -> 18

Solution:

Depth first search — Recursive approach:

def max_path_sum(root):
  if root is None:
    return float("-inf")

  # Edge case:
  # When you are at leaf node. 
  # The return value of this function will be like:
  # 5 + (-infinity) + (-infinity) = (-infinity)
  # You need to catch this before return statement 
  # & that's why you need this. 
  if root.left is None and root.right is None:
    return root.val

  return root.val + max(max_path_sum(root.left), max_path_sum(root.right))

Problem:
Write a function, path_finder, that takes in the root of a binary tree and a target value. The function should return an array representing a path to the target value. If the target value is not found in the tree, then return None. You may assume that the tree contains unique values.

# test_00
a = Node("a")
b = Node("b")
c = Node("c")
d = Node("d")
e = Node("e")
f = Node("f")

a.left = b
a.right = c
b.left = d
b.right = e
c.right = f

#      a
#    /   \
#   b     c
#  / \     \
# d   e     f

path_finder(a, 'e') # -> [ 'a', 'b', 'e' ]

Solution:

Depth first search — Recursive approach — O(n²)

def path_finder(root, target):
    if root is None:
        return None
    if root.val == target:
        return [root.val]
    left_path = path_finder(root.left, target)
    if left_path is not None:
        return [root.val, *left_path]
    right_path = path_finder(root.right, target)
    if right_path is not None:
        return [root.val, *right_path]
    return None

Depth first search — Recursive approach — with append — O(n)

def path_finder(root, target):
    result = _path_finder(root, target)
    if result is None:
        return None
    else:
        return result[::-1]

def _path_finder(root, target):
    if root is None:
        return None
    if root.val == target:
        return [root.val]
    left_path = _path_finder(root.left, target)
    if left_path is not None:
        left_path.append(root.val)
        return left_path
    right_path = _path_finder(root.right, target)
    if right_path is not None:
        right_path.append(root.val)
        return right_path
    return None

Problem:
Write a function, how_high, that takes in the root of a binary tree. The function should return a number representing the height of the tree.
The height of a binary tree is defined as the maximal number of edges from the root node to any leaf node.
If the tree is empty, return -1.

# test_00
a = Node('a')
b = Node('b')
c = Node('c')
d = Node('d')
e = Node('e')
f = Node('f')

a.left = b
a.right = c
b.left = d
b.right = e
c.right = f

#      a
#    /   \
#   b     c
#  / \     \
# d   e     f

how_high(a) # -> 2

Solution:

Depth first search — Recursive approach:

def how_high(root):
    if root is None:
        return -1

    left_height = how_high(root.left)
    right_height = how_high(root.right)
    return 1 + max(left_height, right_height)

Breadth first search — Iterative approach:

from collections import deque

def how_high(root):
    queue = deque([])
    if root is not None:
        queue.append((root, 0))
    max_depth = -1
    while queue:
        node, depth = queue.pop()
        max_depth = max(max_depth, depth)
        if node.left is not None:
            queue.append((node.left, depth + 1))
        if node.right is not None:
            queue.append((node.right, depth + 1))
    return max_depth

Problem:
Write a function, bottom_right_value, that takes in the root of a binary tree. The function should return the right-most value in the bottom-most level of the tree.You may assume that the input tree is non-empty.

# test_00
a = Node(3)
b = Node(11)
c = Node(10)
d = Node(4)
e = Node(-2)
f = Node(1)

a.left = b
a.right = c
b.left = d
b.right = e
c.right = f

#       3
#    /    \
#   11     10
#  / \      \
# 4   -2     1

bottom_right_value(a) # -> 1

Solution:

Breadth first search — Iterative approach:

from collections import deque

def bottom_right_value(root):
  queue = deque([ root ])
  current = None
  while queue:
    current = queue.popleft()
    if current.left is not None:
      queue.append(current.left)
    if current.right is not None:
      queue.append(current.right)
  return current.val

Problem:
Write a function, all_tree_paths, that takes in the root of a binary tree. The function should return a 2-Dimensional list where each subarray represents a root-to-leaf path in the tree.
The order within an individual path must start at the root and end at the leaf, but the relative order among paths in the outer list does not matter.
You may assume that the input tree is non-empty.

# test_00
a = Node('a')
b = Node('b')
c = Node('c')
d = Node('d')
e = Node('e')
f = Node('f')

a.left = b
a.right = c
b.left = d
b.right = e
c.right = f

#      a
#    /   \
#   b     c
#  / \     \
# d   e     f

all_tree_paths(a) # ->
# [ 
#   [ 'a', 'b', 'd' ], 
#   [ 'a', 'b', 'e' ], 
#   [ 'a', 'c', 'f' ] 
# ]

Solution:
Base case 1, what should be returned when base case was hit
Initially, it is tempting to think the answer for base case is just the value of leaf node inside an array. But, that’s not true.
Think of the base case itself as an input. That’s the key.. For example; what should be returned if the tree given to you is just an node d? It should be [[D]] which tells us that their is only one path from root node to leaf node, which is [ ] & since the question is asking us to keep all the paths inside an [ ], which results in [[D]].

Base case 2, what should be returned when base case was null
So, after reading the base case 1, you may think that in case of null node, you should return [[]].
But, NO.When will that inside [ ] comes into picture? When you have an path. Right?
When there is no path itself, then why will the inside [ ] will come in first place? That’s why, the return value in this case is [ ].

Depth first search — Recursive approach:

Observe the 2 base cases. You must write the base case 1 first & then the base case 2. The reason being, If the node is None, then you should catch that first & return an result for that case. Otherwise, if you allow that None to pass through, it will result in error at root.left.

def all_tree_paths(root):
    paths = _all_tree_paths(root)
    for path in paths:
        path.reverse()
    return paths

def _all_tree_paths(root):
    # base case 1
    if root is None:
        return []
    # base case 2
    if root.left is None and root.right is None:
        return [[root.val]]
    all_paths = []
    left_sub_paths = _all_tree_paths(root.left)
    for path in left_sub_paths:
        path.append(root.val)
        all_paths.append(path)
    right_sub_paths = _all_tree_paths(root.right)
    for path in right_sub_paths:
        path.append(root.val)
        all_paths.append(path)
    return all_paths

Problem:
Write a function, tree_levels, that takes in the root of a binary tree. The function should return a 2-Dimensional list where each sublist represents a level of the tree.

# test_00
a = Node('a')
b = Node('b')
c = Node('c')
d = Node('d')
e = Node('e')
f = Node('f')

a.left = b
a.right = c
b.left = d
b.right = e
c.right = f

#      a
#    /   \
#   b     c
#  / \     \
# d   e     f

tree_levels(a) # ->
# [
#   ['a'],
#   ['b', 'c'],
#   ['d', 'e', 'f']
# ]

Solution:
What is level?
— level is all the nodes which are at the same distance(in units of edges) from the root node.
— root starts with level 0, the reason being as per definition, how many edges away is the root node, when you calculate the distance from root node?
0 edges. Let’s follow this subsequentially down the tree & you will end up with.

Breadth first search — Iterative approach:
— As per the definition of level, it’s all the nodes which are at the same distance from the root node. So, when you are doing depth first traversal, will note down the level of each node.
— Breadth first traversal → queue data structure → when we are inserting the node values into queue, will insert the corresponding level of the node also, along with the value.
— When we are popping an value from queue, will pop the node value as well as corresponding level.
That level we pop out, helps us to identify to prepare the result like [ [3], [11, 4], [4, 10, 1] ]
— This is the whole logic of the problem.

def tree_levels(root):
    # Base case
    if root is None:
        return []

    # Iterative step
    levels = []
    queue = [(root, 0)]
    while queue:
        current, level_num = queue.pop(0)
        # When length of levels at which you are is == level of current popped up node,
        # It means, you are at this level for the first time, hence add the node value
        # to new list. Else, just add the element at an index which is equal to current
        # level_num
        if len(levels) == level_num:
            levels.append([current.val])
        else:
            levels[level_num].append(current.val)

        # When you are inserting the child node into queue, the level will be level_num + 1,
        # because, child node will be at +1 level to that of parent level.
        if current.left is not None:
            queue.append((current.left, level_num + 1))

        # When you are inserting the child node into queue, the level will be level_num + 1,
        # because, child node will be at +1 level to that of parent level.
        if current.right is not None:
            queue.append((current.right, level_num + 1))

    return levels

Depth first search — Recursive approach:

def tree_levels(root):
    levels = []
    _tree_levels(root, levels, 0)
    return levels

def _tree_levels(root, levels, level_num):
    if root is None:
        return
    if level_num == len(levels):
        levels.append([root.val])
    else:
        levels[level_num].append(root.val)
    _tree_levels(root.left, levels, level_num + 1)
    _tree_levels(root.right, levels, level_num + 1)

Problem:
Write a function, level_averages, that takes in the root of a binary tree that contains number values. The function should return a list containing the average value of each level.

# test_00
a = Node(3)
b = Node(11)
c = Node(4)
d = Node(4)
e = Node(-2)
f = Node(1)

a.left = b
a.right = c
b.left = d
b.right = e
c.right = f

#       3
#    /    \
#   11     4
#  / \      \
# 4   -2     1

level_averages(a) # -> [ 3, 7.5, 1 ] 

Solution:
— First thing to note is : you can’t do this solution same as that of above & just return the levels[-1].
The reason being: Implementation of leaf_list is that, it only returns the values from the deepest level of the tree,
which is not the same as the list of all leaf nodes. ❌
— You are essentially running a Breadth-First Search (BFS) for level order traversal and grouping nodes by level.
— Your final line, return levels[-1], returns the last list in your levels array, which contains all the nodes at the maximum depth.
This only works correctly if all leaf nodes happen to be at the same maximum depth.
If the tree is unbalanced (meaning some leaf nodes are at shallower depths), your solution will miss them.

Depth first search — Recursive approach:

from statistics import mean

def level_averages(root):
    levels = []
    fill_levels(root, levels, 0)
    avgs = []
    for level in levels:
        avgs.append(mean(level))
    return avgs

def fill_levels(root, levels, level_num):
    if root is None:
        return
    if level_num == len(levels):
        levels.append([root.val])
    else:
        levels[level_num].append(root.val)
    fill_levels(root.left, levels, level_num + 1)
    fill_levels(root.right, levels, level_num + 1)

Breadth first search — Iterative approach:

from statistics import mean
from collections import deque

def level_averages(root):
    levels = []
    fill_levels(root, levels)
    avgs = []
    for level in levels:
        avgs.append(mean(level))
    return avgs

def fill_levels(root, levels):
    if root is None:
        return
    queue = deque([(root, 0)])
    while queue:
        current, level_num = queue.popleft()
        if len(levels) == level_num:
            levels.append([current.val])
        else:
            levels[level_num].append(current.val)
        if current.left is not None:
            queue.append((current.left, level_num + 1))
        if current.right is not None:
            queue.append((current.right, level_num + 1))
    return levels

Problem:
Write a function, leaf_list, that takes in the root of a binary tree and returns a list containing the values of all leaf nodes in left-to-right order.

# test_00
a = Node("a")
b = Node("b")
c = Node("c")
d = Node("d")
e = Node("e")
f = Node("f")

a.left = b
a.right = c
b.left = d
b.right = e
c.right = f

#      a
#    /   \
#   b     c
#  / \     \
# d   e     f

leaf_list(a) # -> [ 'd', 'e', 'f' ] 

Solution:

Depth first search — Iterative approach:

def leaf_list(root):
    if root is None:
        return []
    leaves = []
    stack = [root]
    while stack:
        current = stack.pop()
        if current.left is None and current.right is None:
            leaves.append(current.val)
        if current.right is not None:
            stack.append(current.right)
        if current.left is not None:
            stack.append(current.left)
    return leaves

Depth first search — Recursive approach:

def leaf_list(root):
    leaves = []
    _leaf_list(root, leaves)
    return leaves
def _leaf_list(root, leaves):
    if root is None:
        return
    if root.left is None and root.right is None:
        leaves.append(root.val)
    _leaf_list(root.left, leaves)
    _leaf_list(root.right, leaves)