Flashcards for "Trees and Tries"

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        
        self.isBalanced=True
        def height_of_tree(node):
            
            if node is None:
                return 0
            
            h_left=height_of_tree(node.left)
            h_right=height_of_tree(node.right)

            if abs(h_right-h_left)>1:
                self.isBalanced=False
            
            return 1+(max(h_left, h_right))
        
        height_of_tree(root)
        return self.isBalanced

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        
        if not root:
            return []

        q=deque([(root, 0)])
        ans=[]

        while q:
            num_nodes=len(q)
            ans.append([])
            for _ in range(num_nodes):
                node, level = q.popleft()
                ans[-1].append(node.val)

                if node.left:
                    q.append((node.left, level+1))
                if node.right:
                    q.append((node.right, level+1))

        return ans 

No answer provided.

class Solution:
    def rightSideView(self, root: Optional['TreeNode']) -> List[int]:
        """
        Return the values visible from the right side of a binary tree.
        DFS: traverse right→left; record first node seen at each depth.
        """
        view: List[int] = []

        def dfs(node: Optional['TreeNode'], depth: int) -> None:
            if not node:
                return
            if depth == len(view):        # first visit at this depth
                view.append(node.val)
            dfs(node.right, depth + 1)     # right subtree first
            dfs(node.left,  depth + 1)

        dfs(root, 0)
        return view

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        
        if not preorder or not inorder:
            return None
        
        root_val=preorder[0]
        root=TreeNode(root_val)

        mid=inorder.index(root_val)

        root.left=self.buildTree(preorder[1:mid+1], inorder[:mid])
        root.right=self.buildTree(preorder[mid+1:], inorder[mid+1:])
    
        return root

class Solution:
    def goodNodes(self, root: TreeNode) -> int:
        def count_good_nodes(node, max_val):
            if not node:
                return 0
            
            # A node is "good" if its value is greater than or equal to the maximum value seen so far.
            good = 1 if node.val >= max_val else 0
            
            # Update max value seen so far
            max_val = max(max_val, node.val)
            
            # Recursively count good nodes in left and right subtrees
            good += count_good_nodes(node.left, max_val)
            good += count_good_nodes(node.right, max_val)
            
            return good

        return count_good_nodes(root, root.val)

class TrieNode:
    def __init__(self):
        self.is_word = False
        self.children = {}

class WordDictionary:
    def __init__(self):
        self.root = TrieNode()

    def addWord(self, word: str) -> None:
        curr = self.root
        for char in word:
            if char not in curr.children:
                curr.children[char] = TrieNode()
            curr = curr.children[char]
        curr.is_word = True  # Mark the end of the word

    def _search_helper(self, word, node):
        curr = node

        for index, char in enumerate(word):
            if char == ".":
                for child in curr.children.values():
                    if self._search_helper(word[index + 1:], child):
                        return True
                return False  # No matches found

            if char not in curr.children:
                return False
            
            curr = curr.children[char]  # Move to next character

        return curr.is_word  # Check if it's a valid word

    def search(self, word: str) -> bool:
        return self._search_helper(word, self.root)

class Solution:
    def diameterOfBinaryTree(self, root: Optional['TreeNode']) -> int:
        """
        Post‑order DFS: for each node compute its subtree height.
        Diameter = max(left_height + right_height) over all nodes.
        """
        if not root:
            return 0

        diameter = 0

        def dfs(node: Optional['TreeNode']) -> int:
            nonlocal diameter
            if not node:
                return 0
            left_h  = dfs(node.left)
            right_h = dfs(node.right)
            diameter = max(diameter, left_h + right_h)
            return 1 + max(left_h, right_h)

        dfs(root)
        return diameter

class TrieNode:

    def __init__(self):
        self.is_word=False
        self.children={}

class Trie:

    def __init__(self):
        self.root=TrieNode()

    def insert(self, word: str) -> None:
        curr=self.root
        for char in word:
            if char not in curr.children:
                curr.children[char]=TrieNode()
            curr=curr.children[char]
        
        curr.is_word=True

    def search(self, word: str) -> bool:
        curr=self.root
        for char in word:
            if char not in curr.children:
                return False
            curr=curr.children[char]
        
        return curr.is_word

    def startsWith(self, word: str) -> bool:
        curr=self.root
        for char in word:
            if char not in curr.children:
                return False
            curr=curr.children[char]
            
        return True

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        
        if root is None:
            return root

        root.left, root.right = root.right, root.left
        self.invertTree(root.left)
        self.invertTree(root.right)
        return root

class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        stack = []
        
        while True:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            k -= 1
            if k==0:
                return root.val
            root = root.right

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        

        parent_val=root.val
        p_val=p.val
        q_val=q.val

        if parent_val>p_val and parent_val>q_val:
            return self.lowestCommonAncestor(root.left, p, q)
        elif parent_val<p_val and parent_val<q_val:
            return self.lowestCommonAncestor(root.right,p,q)
        else:
            return root

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0
        return 1+max(self.maxDepth(root.left), self.maxDepth(root.right))

class Solution(object):
    def isSameTree(self, p, q):
        if p==None: return q==None
        if q==None: return p==None
        return p.val==q.val and self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)

class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        self.tree=[]

        def dfs(node):
            if node == None:
                self.tree.append("X")
                return
            self.tree.append(str(node.val))
            dfs(node.left)
            dfs(node.right)
            return 
        
        dfs(root)
        return "#".join(self.tree)

        

    def deserialize(self, data):
        """
        Decodes your encoded data to a tree.

        :type data: str
        :rtype: TreeNode
        """

        def dfs(tree_iter):
            """
            Helper function for depth-first search deserialization.
            """
            val = next(tree_iter)
            if val == "X":
                return None

            node = TreeNode(int(val))
            node.left = dfs(tree_iter)
            node.right = dfs(tree_iter)
            return node

        tree_iter = iter(data.split("#"))
        return dfs(tree_iter)

class Solution:
    def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:
        if not s: 
            return False
        if self.isSameTree(s, t): 
            return True
        return self.isSubtree(s.left, t) or self.isSubtree(s.right, t)

    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if p and q:
            return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
        return p is q

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        
        return self.isValidTree(root, -float("inf"), float("inf"))

    
    def isValidTree(self, node, min_val, max_val):

        if node is None:
            return True
        
        if node.val<=min_val or node.val>=max_val:
            return False
        
        return self.isValidTree(node.left, min_val, node.val) and self.isValidTree(node.right, node.val, max_val)