Binary Tree in Python

Definition

A binary tree might be the simplest tree data structure. It only have three attributes: the value of the node, its left and right child node. If its child node is None, this child node do not have value or child nodes anymore.

Here is the definition of a typical binary tree from LeetCode:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

Similar to linked list, binary tree is also a one direction data type. Once moved to its child node, there is no way to trace back, except going through it from the head node again.

In LeetCode, the input is a list-like binary tree, which is probably difficult to understand at the first glance. For example, inputs wirtten as [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15] and [1, 2, 3, 4, 5, null, 7, 8, 9, 10, 11, 12] should be interpretered as image below.

It is not extremely significant, however, since we just need to cope with its attributes in our implementation.

Binary Tree Inorder Traversal

94. Binary Tree Inorder Traversal (Easy)

This problem is really a great intro to the understandment of binary tree. It require atraversal of given binary tree.

By inspecting the output, it should be implemented in depth first search (DFS), with left child node searched first. This sounds like nonsense as the input is given layer by layer. But this really confused me at very first.

Unquestionably, this problem could be solved by recursion.

# Recursive Solution
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        def re(lis, tree):
            if tree:
                re(lis, tree.left) # Go to its left child node
                lis.append(tree.val)
                re(lis, tree.right) # Go to its right child node
            return lis
        return re([], root)

Don’t need to worry about what if it’s left or right attribute is null, it would pass in next function call.

Some Similar Questions

Same Tree

We can apply similar logic to the question 100. Same Tree (Easy).

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        def re(t1, t2):
            if not t1 and not t2:
                return True
            elif t1 and t2:
                if t1.val != t2.val:
                    return False
                if re(t1.left, t2.left):
                    return re(t1.right, t2.right)
            else:
                return False
        return re(p, q)

Symmetric Tree

And the question 101. Symmetric Tree (Easy).

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        def re(t1, t2):
            if not t1 and not t2:
                return True
            elif t1 and t2:
                if t1.val != t2.val:
                    return False
                if re(t1.left, t2.right):
                    return re(t1.right, t2.left)
            else:
                return False
        return re(root.left, root.right)

Maximum Depth of Binary Tree

104. Maximum Depth of Binary Tree (Easy)

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        def re(t):
            if not t:
                return 0
            left_depth = re(t.left)
            right_depth = re(t.right)
            return max(left_depth, right_depth) + 1
        return re(root)

Recursion is probably the simplist way to manage a binary tree, and there is no waste on calculating same base cases.

Balanced Binary Tree

110. Balanced Binary Tree (Easy)

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def get_length(a):
            if not a:
                return 0
            left_depth = get_length(a.left)
            right_depth = get_length(a.right)
            l = max(left_depth, right_depth) + 1
            return l
        
        def re(t):
            if not t:
                return True
            left_len = get_length(t.left)
            right_len = get_length(t.right)
            if abs(left_len - right_len) > 1:
                return False
            if re(t.left):
                return re(t.right)
            else:
                return False
        return re(root)

Here, for the first time, comes some waste calculation.

References

1. Binary Tree Inorder Traversal - LeetCode
2. Introduction to Data Structure - Binary Tree - LeetCode
3. Trees - Composing Programs
4. Tree Data Structure