# Binary Tree

## solution 1: naive recursion

Key observations:

the first node of preorder is the root node

find the index of root from inorder list, then left part will be the left subtree and right part will be the right subtree.

For the preorder subtrees, if nodes in the left part of the inorder subtree, it is a left preorder subtree. Else, it is a right preorder subtree.

`# Definition for a binary tree node.# class TreeNode:#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneclass Solution:    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:        def helper(inorder, preorder):            if not inorder:return None            root = preorder[0]            idx = inorder.index(root)            left_inorder, right_inorder = inorder[:idx], inorder[idx+1:]            left_preorder, right_preorder= [], []            left_inorder_set = set(left_inorder)            for node in preorder[1:]:                if node in left_inorder_set:                    left_preorder.append(node)                else:                    right_preorder.append(node)            left = helper(left_inorder, left_preorder)            right = helper(right_inorder, right_preorder)            root_node = TreeNode(root)            root_node.left = left            root_node.right = right            return root_node        return helper(inorder, preorder)`
`def buildTree(self, preorder, inorder):    if inorder:        ind = inorder.index(preorder.pop(0))        root = TreeNode(inorder[ind])        root.left = self.buildTree(preorder, inorder[0:ind])        root.right = self.buildTree(preorder, inorder[ind+1:])        return root`

Or using the below code to get rid of pop(0)

`# Definition for a binary tree node.# class TreeNode:#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneclass Solution:    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:        def helper(preorder, inorder):            if not inorder:return None            idx = inorder.index(preorder.pop())            root = TreeNode(inorder[idx])            root.left = helper(preorder, inorder[:idx])            root.right = helper(preorder, inorder[idx+1:])            return root        return helper(preorder[::-1], inorder)`

## 101. Symmetric Tree

`# Definition for a binary tree node.# class TreeNode:#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneclass Solution:    def isSymmetric(self, root: TreeNode) -> bool:        if root is None:return True        def helper(node1, node2):            if node1 is None and node2 is None:return True            if node1 is None and node2 is not None:return False            if node1 is not None and node2 is None:return False            if node1.val!=node2.val:return False            return helper(node1.left,node2.right) and helper(node1.right, node2.left)        return helper(root.left, root.right)`

Above code can be slightly modified to make it shorter as below

`class Solution:    def isSymmetric(self, root: TreeNode) -> bool:        if root is None:return True        def helper(node1, node2):            if node1 and node2:                return node1.val==node2.val and helper(node1.left,node2.right) and helper(node1.right, node2.left)            # at lease one is None            else:return node1 == node2        return helper(root.left, root.right)`

The code above is a recursive code, for the iterative code can be found here.

# Link to previous binary tree article

--

--

## More from Jimmy (xiaoke) Shen

Data Scientist/MLE/SWE @takemobi

Love podcasts or audiobooks? Learn on the go with our new app.