# Binary Tree

545. Boundary of Binary Tree

`# Definition for a binary tree node.# class TreeNode:#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneclass Solution:    def boundaryOfBinaryTree(self, root: TreeNode) -> List[int]:           if root is None:return []        if root.left is None and root.right is None:return [root.val]        left, leaf, right = [root.val], [], []        def get_boundary(node, side='left'):            if node is None:return            if side =='left':                if node.left or node.right:left.append(node.val)                if node.left is None:                    get_boundary(node.right)                else:                    get_boundary(node.left)            else:                if node.left or node.right:right.append(node.val)                if node.right is None:                    get_boundary(node.left,'right')                else:                    get_boundary(node.right,'right')        def get_leaf(node):            if node is None:return            get_leaf(node.left)            if node.left is None and node.right is None:                leaf.append(node.val)            get_leaf(node.right)        get_boundary(root.left, 'left')        get_leaf(root)        get_boundary(root.right,'right')        return left+leaf+right[::-1]`

103. Binary Tree Zigzag Level Order Traversal

`# Definition for a binary tree node.# class TreeNode:#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneclass Solution:    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:        res = []        if root is None:return []        def bfs():            current_level = [root]            i = 0            while current_level:                new_level = []                if i%2==0:res.append([node.val for node in current_level])                else:res.append([node.val for node in current_level[::-1]])                for node in current_level:                    if node.left:                        new_level.append(node.left)                    if node.right:                        new_level.append(node.right)                i+=1                current_level = new_level        bfs()        return res`

1008. Construct Binary Search Tree from Preorder Traversal

`# Definition for a binary tree node.# class TreeNode:#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneclass Solution:    def bstFromPreorder(self, preorder: List[int]) -> TreeNode:        def helper(preorder):            if not preorder:return None            if len(preorder)==1:                return TreeNode(preorder[0])            root_val = preorder[0]            left =  [val for val in preorder[1:] if val<root_val ]            right = [val for val in preorder[1:] if val>root_val]            left_node = helper(left)            right_node = helper(right)            root = TreeNode(root_val)            root.left = left_node            root.right = right_node            return root        return helper(preorder)`

449. Serialize and Deserialize BST

`# Definition for a binary tree node.# class TreeNode:#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneclass Codec:def serialize(self, root: TreeNode) -> str:        """Encodes a tree to a single string.        """        if root is None:return "#"*100        nodes = []         def preorder(node):            if node is None:return            nodes.append(str(node.val))            preorder(node.left)            preorder(node.right)        preorder(root)        #print(nodes)        return ','.join(nodes)def deserialize(self, data: str) -> TreeNode:        """Decodes your encoded data to tree.        """        if data == "#"*100:return None        nodes = data.split(',')        vals = collections.deque()        for node in nodes:            vals.append(int(node))        def build(min_val, max_val):            if vals and min_val < vals[0] < max_val:                val = vals.popleft()                node = TreeNode(val)                node.left = build(min_val, val)                node.right = build(val, max_val)                return node            return None`

The above code works

This code is NOT working

`# Definition for a binary tree node.# class TreeNode:#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneclass Codec:def serialize(self, root: TreeNode) -> str:        """Encodes a tree to a single string.        """        if root is None:return "#"*100        nodes = []         def preorder(node):            if node is None:return            nodes.append(str(node.val))            preorder(node.left)            preorder(node.right)        preorder(root)        #print(nodes)        return ','.join(nodes)def deserialize(self, data: str) -> TreeNode:        """Decodes your encoded data to tree.        """        if data == "#"*100:return None        nodes = data.split(',')        def helper(preorder):            if not preorder:return None            if len(preorder)==1:return TreeNode(preorder[0])            root_val = preorder[0]            rest = preorder[1:]            #idx = bisect.bisect_left(rest, root_val)            left = [val for val in rest if val<root_val]            right = [val for val in rest if val>root_val]            root = TreeNode(root_val)            root.left = helper(left)            root.right = helper(right)            return root        return helper(nodes)`

236. Lowest Common Ancestor of a Binary Tree

Naive approach

`# Definition for a binary tree node.# class TreeNode:#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneclass Solution:    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':        if p is q:return p        if p is root or q is root:return root        dummy = None        parents = {}        found = [False, False]        parents_p = set()        parents_q = set()        def traverse(node, parent=dummy, level=0):            if node is None:return            else:                if node == p:                    parents_p.add((level, p))                    found[0] = True                elif node == q:                    parents_q.add((level, q))                    found[1] = True                parents[node] = (level-1, parent)                if found[0] and found[1]:return                traverse(node.left, node, level+1)                traverse(node.right, node, level+1)        traverse(root)                node = p        while node is not None:            parents_p.add(parents[node])            _, node = parents[                node]        node = q        while node is not None:            parents_q.add(parents[node])            _, node = parents[node]        _, lca_node = max(parents_p & parents_q)        return lca_node`

A much better one from here

`class Solution(object):    def lowestCommonAncestor(self, root, p, q):        if not root: return None        if p == root or q == root:            return root        left = self.lowestCommonAncestor(root.left, p , q)        right = self.lowestCommonAncestor(root.right, p , q)                if left and right:            return root        if not left:            return right        if not right:            return left`

173. Binary Search Tree Iterator

As for BST, the in order traverse can guarantee the output is in a sorted order. So a naive solution will be inorder traverse and put everything in a stack then pop one item each time.

However, this solution will have a complexity of O(n) during the class instantiation. Hence, it is not a very good design. Although this design, the amortized complexity for next is also O(1), a better design can make the time more uniformly distributed.

`# Definition for a binary tree node.# class TreeNode:#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneclass BSTIterator:    def _inorder(self, node):        if node is None:return        self._inorder(node.left)        self._stack.append(node.val)        self._inorder(node.right)    def __init__(self, root: TreeNode):        self._stack = []        self._inorder(root)        self._stack = self._stack[::-1]    def next(self) -> int:        """        @return the next smallest number        """        if self._stack:return self._stack.pop()        else:return -1    def hasNext(self) -> bool:        """        @return whether we have a next smallest number        """        return len(self._stack)>0# Your BSTIterator object will be instantiated and called as such:# obj = BSTIterator(root)# param_1 = obj.next()# param_2 = obj.hasNext()`

A better design from here

`class BSTIterator(object):  def __init__(self, root):    self.stack = []    self._extract(root)  def _extract(self, root):    while root:      self.stack.append(root)      root = root.left  def hasNext(self):    return len(self.stack) > 0  def next(self):    node = self.stack.pop()    if node.right:      self._extract(node.right)    return node.val`

102. Binary Tree Level Order Traversal

`# Definition for a binary tree node.# class TreeNode:#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneclass Solution:    def levelOrder(self, root: TreeNode) -> List[List[int]]:        res = []        if root is None:return []        def bfs():            current_level = [root]            while current_level:                this_res = []                new_level = []                for node in current_level:                    if node:this_res.append(node.val)                    if node.left:new_level.append(node.left)                    if node.right:new_level.append(node.right)                res.append(this_res)                current_level = new_level        bfs()        return res`

Data Scientist/MLE/SWE @takemobi

## More from Jimmy Shen

Data Scientist/MLE/SWE @takemobi