Posts

LeetCode 669 | Trim a Binary Search Tree | Python Solution

 Introduction: In this blog post, we'll discuss a common problem in binary search trees, which is trimming a tree within a given range. We'll go over a Python solution using recursion to accomplish this task. Problem Statement: Given a binary search tree (BST) with the root node, low, and high values, the task is to trim the tree such that all the nodes' values are within the range [low, high]. You can assume that the given tree is a non-empty BST and the range low <= high. Here's an example of a TreeNode class in Python that we'll be working with: # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution ( object ): def trimBST ( self , root, low, high): """ :type root: TreeNode :type low: int :type high: int :rtype: TreeNode &q

LeetCode 2415 | Reverse Odd Levels of Binary Tree | Python Solution

Image
 LeetCode Problem Link : https://leetcode.com/problems/reverse-odd-levels-of-binary-tree/description/ Video Solution :  https://www.youtube.com/watch?v=oidCQx8j7GE # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution ( object ): def reverseOddLevels ( self , root): """ :type root: Optional[TreeNode] :rtype: Optional[TreeNode] """ def helper (root1,root2, depth): if root1 is None and root2 is None : return None if depth % 2 != 0 : tmp = root1 . val root1 . val = root2 . val root2 . val = tmp helper(root1 . left,root2 . right, depth + 1 ) helper(root1 . right,root2 . left, depth + 1 ) helper(root . lef

LeetCode - 1026 Maximum Difference Between Node and Ancestor | Python Solution

Image
LeetCode 1026 Python Solution  LeetCode : https://leetcode.com/problems/maximum-difference-between-node-and-ancestor/description/ # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution(object): max_diff = 0 def maxAncestorDiff(self, root): """ :type root: TreeNode :rtype: int """ def helper(root , cmin , cmax): if root is None : return float( 'inf' ) ,float( '-inf' ) #Traverse Tree left_min , left_max = helper(root.left , cmin , cmax) right_min , right_max = helper(root.right , cmin ,cmax) cmin = min(root.val , left_min , right_min ) cmax= max(root.val , left_max , right_max ) self.max_diff = max(self.max_diff

LeetCode 662 | Maximum Width of Binary Tree | Python Solution

Image
 LeetCode Link : https://leetcode.com/problems/maximum-width-of-binary-tree/description/ Video Solution : https://www.youtube.com/watch?v=9NYXVzPCH04&t=2s # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution(object): def widthOfBinaryTree(self, root : TreeNode) -> int: """ :type root: TreeNode :rtype: int """ width_map = defaultdict(list) def helper(root , depth , column): if root is None : return # Add column position to map # width_map[1] = [0,1] <- 0 for 3 and 1 for 2. width_map[depth].append(column) left_col = column* 2 # Calculate Left Column Position right_col = column* 2 + 1 # Calculate Righ

LeetCode 687 Longest Univalue Path | Python Solution

 LeetCode : https://leetcode.com/problems/longest-univalue-path/ Youtube Solution :  Youtube Solution Link # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution ( object ): longest_path = 0 def longestUnivaluePath ( self , root): """ :type root: TreeNode :rtype: int """ self . helper(root) return self . longest_path def helper ( self ,root) : if root is None : return 0 left = self . helper(root . left) right = self . helper(root . right) if root . left and root . left . val == root . val : left_path = 1 + left else : left_path = 0 if root . right and root . right . val == root . val: right_path =

LeetCode | Hard | 1932 Merge BSTs to Create Single BST | Python Solution

  Approach Indentify your root tree from where merging will being . Now from remaining trees , apply helper function to merge. If final tree is valid BST then return tree else return None. Youtube Link :  https://www.youtube.com/watch?v=3QC5L5W0Lhk # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution(object): is_merged = False def canMerge(self, trees): """ :type trees: List[TreeNode] :rtype: TreeNode """ if len(trees) == 1 : return trees[ 0 ] #Find List of Leaf Nodes all_leaves_node = set() for tree in trees : if tree.left : all_leaves_node.add(tree.left.val) if tree.right : all_leaves_node.add(tree.right.val) # Find start

LeetCode : 1302 Deepest Leaves Sum | Depth First Search (DFS) Solution with Python

  LeetCode Problem : https://leetcode.com/problems/deepest-leaves-sum/description/ # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution(object): height = 0 result = 0 def deepestLeavesSum(self, root): """ :type root: TreeNode :rtype: int """ self.helper(root, 1 ) return self.result def helper(self, root , depth ) : if root is None : return 0 # Check if it is a Leaf Node and Depth is greater than Heigh # Then update result variable if depth > self.height and root.left is None and root.right is None : self.height = depth self.result = root.val elif depth == self.height: # If nodes are at same depth then , ad