Binary Tree traversals – recursion

Srinivas Reddy Thatiparthy — Tue, 05 Nov 2024 12:19:26 +0000

Tree traversals

A Binary tree is a hierarchical data structure that contains at most two children.
There are three different ways of visiting the binary tree nodes,

Pre order traversal – ( Node, Left, Right)
In order traversal – (Left, Node, Right)
Post order traversal – (Left, Right, Node)

Pre Order Traversal

def pre_order(root, result):
    if root is None:
        return result
    result.append(root.val)
    pre_order(root.left, result)
    pre_order(root.right, result)
    return result

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        return pre_order(root, [])

In Order Traversal

def inorder(root, result):
    if not root:
        return result
    inorder(root.left, result)
    result.append(root.val)
    inorder(root.right, result)
    return result

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        return inorder(root, [])

Post Order Traversal

def post_order(root, result):
    if root is None:
        return result
    post_order(root.left, result)
    post_order(root.right, result)
    result.append(root.val)
    return result

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        return post_order(root, [])

All these recursion solutions are trivial. But could you come up with iterative solutions for these traversals?

Leetcode – 56: Merge intervals

Srinivas Reddy Thatiparthy — Tue, 05 Nov 2024 11:20:34 +0000

Merge Intervals

Given a list of intervals, how can we produce a resultant list of intervals that contains only non -overlapping intervals.

Take, for example, that we have [ [1,4], [4,5] ], here 4 is overlapping both intervals.
So the resultant will be [ [1,5] ].
Let us consider another example, [ [1,3],[2,6],[8,10],[15,18] ]. Here 2 exists between [1,3].
So the resultant list becomes [ [1,6], [8,10],[15,18] ].

And the problem does not specify that the input is sorted. We have to sort the input before merging.
First we sort the intervals by the first item – start of the interval.While iterating, we check if the new item exists between current interval, if it does, we expand the current interval. Otherwise, the first interval is added to the result list and new item becomes the current interval. Iterate until the list is complete.

Finally, the last item that remained will be added to result at the end.

def merge(intervals):
    intervals = sorted(intervals, key=lambda x: x[0])
    current_interval = intervals[0]
    result = []
    for index in range(1, len(intervals)):
        if current_interval[0]<=intervals[index][0]<=current_interval[1]:
            if intervals[index][1] >=current_interval[1]:
                current_interval = [current_interval[0], intervals[index][1]]
        else:
            result.append(current_interval)
            current_interval = intervals[index]
    result.append(current_interval)
    return result
class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        return merge(intervals)