DEV Community

loading...
Cover image for Binary Tree Practice in Python: Mirror Tree

Binary Tree Practice in Python: Mirror Tree

erikhei profile image Whiteboarding with Erik Updated on ・4 min read

<< #20 Breadth-First Search | View Solution on GitHub | #22 Sum of Three+ >>

Trees mirrored in lake
(Image: FollowingNature on Flickr)

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).
Enter fullscreen mode Exit fullscreen mode

Let's look at some examples.

tree example symmetrical
(Image: LeetCode)

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.

tree example unsymmetrical
(Image: LeetCode)

In the above tree, the nodes with 3 are not organized to mirror each other. Passing the root would yield False.

1. Strategy

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:

tree example symmetrical

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.

2. Setup

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 left and right pointer, which are initialized to None.

class TreeNode:
  def __init__(self, data):
    self.data = data
    self.left = None
    self.right = None
Enter fullscreen mode Exit fullscreen mode

Next, we define our method, which takes in one value: the root node of the tree.

def is_mirror(root):
  pass
Enter fullscreen mode Exit fullscreen mode

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.left and root.right to start.

def is_mirror(root):
  return check_halves(root.left, root.right)
Enter fullscreen mode Exit fullscreen mode

3. Traversal

As with most tree traversals, we'll be using recursion. Start by defining our helper method that takes in a left and right tree.

def check_halves(left, right):
Enter fullscreen mode Exit fullscreen mode

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 True.

def check_halves(left, right):
  if not left and not right:
    return True
Enter fullscreen mode Exit fullscreen mode

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:
Enter fullscreen mode Exit fullscreen mode

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)
Enter fullscreen mode Exit fullscreen mode

Then, we check to see if they are both True. This can be achieved with an and statement.

      return left_half and right_half
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

4. Test it Out

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)
Enter fullscreen mode Exit fullscreen mode

Now we just have to call print(is_mirror(tree1)) and it will print True. Success!

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)
Enter fullscreen mode Exit fullscreen mode

Printing 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.

<< #20 Breadth-First Search | View Solution on GitHub | #22 Sum of Three+ >>

Erik Heikkila is a Teaching Assistant at General Assembly. This blog is not associated with GA.

Discussion (0)

pic
Editor guide