In the previous article, we discussed the differences between breadth- and depth-first search for trees and graph problems. Today, we're going to actually look at a sample problem, and given our new toolbox of search strategies, figure out the best way to implement a solution.
Here's the problem from LeetCode.
# Given the root of a binary tree, check whether it is # a mirror of itself (i.e., symmetric around its center).
Let's look at some examples.
Giving the function the root of the above tree would yield
True, since the values in the left half of the tree mirror the values in the right.
In the above tree, the nodes with 3 are not organized to mirror each other. Passing the root would yield
As with binary tree problems, the first thing we want to ask is if we should use breadth- or depth-first search. At first glance, you might think BFS would make sense, seeing that all the nodes are the same across the first two levels. But once we look at the third level with the nodes
3, 4, 4, 3, suddenly, it gets more complicated. Instead, what if we split the tree into two halves and ran a depth-first-search on each half? Let's look at the first example again:
If we were to look at the left half, depth-first-traversal would read the nodes in the order:
2, 3, 4. At the same time, we can travel down the right side of the tree and print the same
2, 3, 4. We then conclude the tree is symmetrical.
The first thing we'll need is our
TreeNode class. As always, it will take
data, the value we want to store on the node, and then a
right pointer, which are initialized to
class TreeNode: def __init__(self, data): self.data = data self.left = None self.right = None
Next, we define our method, which takes in one value: the root node of the tree.
def is_mirror(root): pass
Remember how we said we would split the tree into two halves, and then check the nodes in each half? We'll do that by calling a recursive helper method,
check_halves. This method takes a left and right node, which will be
root.right to start.
def is_mirror(root): return check_halves(root.left, root.right)
As with most tree traversals, we'll be using recursion. Start by defining our helper method that takes in a
def check_halves(left, right):
What is our base case? The simplest example would be a tree with only the root node, whose left and right halves are both
None. In this case, we return
def check_halves(left, right): if not left and not right: return True
What's next? We want to check that there are both a left and right node, and that their values match. These can be put in the same if statement, but I'll separate them for clarity.
def check_halves(left, right): if not left and not right: return True if left and right: if left.data == right.data:
Next, we recurse! Here, we'll do a depth-first traversal on the left and right halves of the tree.
left_half = check_halves(left.left, right.right) right_half = check_halves(left.right, right.left)
Then, we check to see if they are both
True. This can be achieved with an
return left_half and right_half
Finally, we return the False if the previous
if condition was not met. Altogether, our helper method looks like this:
def check_halves(left, right): if not left and not right: return True if left and right: if left.data == right.data: left_half = check_halves(left.left, right.right) right_half = check_halves(left.right, right.left) return left_half and right_half return False
The following code will build the tree from the example.
tree1 = TreeNode(1) tree1.left = TreeNode(2) tree1.right = TreeNode(2) tree1.left.left = TreeNode(3) tree1.right.right = TreeNode(3) tree1.left.right = TreeNode(4) tree1.right.left = TreeNode(4)
Now we just have to call
print(is_mirror(tree1)) and it will print
Let's try a tree that isn't symmetrical, like the second example. The two nodes with the value
3 aren't positioned to mirror each other.
tree2 = TreeNode(1) tree2.left = TreeNode(2) tree2.right = TreeNode(2) tree2.left.left = TreeNode(3) tree2.right.left = TreeNode(3)
is_mirror(tree2) should give us
False. The same will work if we change any values in the first tree so that they don't match left and right.
That's it for this week, I hope this was a good lesson on how to use DFS concepts to solve a Binary Tree problem. In a future article, we'll take a look at a problem where a breadth first approach would work better.
Erik Heikkila is a Teaching Assistant at General Assembly. This blog is not associated with GA.