Teaching Kids Programming – Longest Path in Binary Tree via Recursive Depth First Search Algorithm

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a binary tree root, return the longest path between any two nodes in the tree.

Constraints
n ≤ 100,000 where n is the number of nodes in root
Example 1
Input
root = [0, [1, null, null], [2, [3, [4, null, null], null], [0, null, null]]]
Output
5

Explanation
A longest path is [1, 0, 2, 3, 4]

Example 2
Input
root = [0, null, [2, [3, [4, null, null], null], [0, null, [6, null, [7, null, null]]]]]
Output
6
Explanation
A longest path is [4, 3, 2, 0, 6, 7]

Think about the choices you can make at any node.
Either it is at the top of the longest path or it allows another node to be at the top.
height, diameter??

Longest Path in Binary Tree via Recursive Depth First Search Algorithm

In previous post, we are finding the longest path with even nodes, so the algorithm (Recursive Depth First Search Algorithm) can be applied to solve this problem as well. We can recursively traverse the binary tree and compute the longest path as L+R+1 where L and R is the longest path starting from the current node respectively.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# class Tree:
#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def longestPathBinaryTree(self, root):
        ans = 0
 
        def dfs(root):
            if not root:
                return 0
            nonlocal ans
            L, R = dfs(root.left), dfs(root.right)
            ans = max(ans, L + R + 1)
            return 1 + max(L, R)
 
        dfs(root)
        return ans

# class Tree:
#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def longestPathBinaryTree(self, root):
        ans = 0

        def dfs(root):
            if not root:
                return 0
            nonlocal ans
            L, R = dfs(root.left), dfs(root.right)
            ans = max(ans, L + R + 1)
            return 1 + max(L, R)

        dfs(root)
        return ans

The DFS is usually implemented in Recursion and each node of the binary tree is visited once and thus the time and space complexity is O(N). Space is due to stack usage from Recursion.

Longest Path Problems in Binary Tree

• Teaching Kids Programming – Longest Even Value Path in Binary Tree via Graph Breadth First Search Algorithm
• Teaching Kids Programming – Longest Even Value Path in Binary Tree using Recursive Depth First Search Algorithm
• Teaching Kids Programming – Longest Path in Binary Tree via Recursive Depth First Search Algorithm
• Teaching Kids Programming – Longest Path in Binary Tree via Diameter Algorithm (DFS + BFS)

–EOF (The Ultimate Computing & Technology Blog) —