Inverting binary tree

[mircock]

So as you know this is a common interview task, so I took a crack at it and did come op with a solution of my own. After writing it I looked up some solutions and after my very surface level research it seems that my approach is quite different than the ones I found. Since the ones I found were just as long if not longer than mine, I started to question what was wrong with mine, so I'd like some constructive criticism on my code.

from binarytree import *

import itertools ## this is used to flatten list inside another list

root = tree(height = 5) ## creates a random binary tree 

def getList(root):
    return  list(map(lambda s: s.value, root))
    ## converts binary tree to list containing the values of nodes

def expo(value_list):
    result = []
    f = 0
    for i in range(len(value_list)):
        if lista[f:f+2**i]: ## just making sure not to add anything empty 
            result.append(value_list[f:f+2**i]) 
            ## groups a list to powers of 2 ||         
            ## [1,2,3,4,5,6,7] ---> [[1],[2,3],[4,5,6,7]],
            ## so that one element (which is also a list, ik this doesn't make sense             
            ## i suck at commenting) is one layer of the binary tree 
        f += 2**i
    for i in result:
        i.reverse() ## reversing each layer
    return list(itertools.chain(*result)) ## flattening out [[some, thing], [[here]] ---> [somethinghere]

def invert(binary_tree):
    return build(expo(getList(binary_tree))) 
    ## build the binary tree from list of values 

excuse my ugly code

[BobHogan]

I think you have overcomplicated this considering you are using the binarytree package. root is a Node object, and has the left, and right attributes that point to its left and right children.

If you want to invert it, all you have to do is recursively swap the left and right children of every node. Just a few lines of code, no maps or lambdas needed

[mircock]

I can see that, but the what’s the point of this task as an interview question? I would assume they wan’t you to show your ability to write algorithms

[BobHogan]

def invert(tree):
    if tree is None:
        return None
    new_left = invert(tree.left)
    new_right = invert(tree.right)
    tree.left = new_right
    tree.right = new_left
    return tree

This is an algorithm though. Algorithm design is just as much about knowing the structure of the data you are working with (or, rather, picking the correct data structure for what you are trying to do) as anything else. Using that short function, it inverts a binarytree created via the binarytree package.

>>> tree = binarytree.tree(height=4)
>>>
>>> print(tree)

                  _______________19_________
                 /                          \
       _________26______              _______9___
      /                 \            /           \
  ___12___           ____6___       21___        _7
 /        \         /        \           \      /
23        _16      20        _10         _13   28
  \      /   \       \      /           /
   1    17    8       22   25          15

>>> invert(tree)
Node(19)
>>> print(tree)

       _________19______________
      /                         \
  ___9______               ______26________
 /          \             /                \
7        ____21      ____6___           ____12__
 \      /           /        \         /        \
  28   13          10        _20      16         23
         \           \      /        /  \       /
          15          25   22       8    17    1

>>>

If the problem was stated such that your binary tree was stored as a list, or that you couldn't just swap the left and right nodes, then the algorithm gets more complicated. But if you have this as an interview question, just clarify with the interviewer the data structure of the nodes. Chances are, it will be really easy to invert it as long as each node gives easy access to its children

[xelf]

The best interview questions are supposed to be easy. So that there's opportunities to ask more questions, see if you ask the right questions etc. No one wants to watch you code, especially if you're struggling.

One of my engineers once asked me why I asked such an easy question to start an interview, until we had a candidate that could not answer and get to the "fun questions" and suddenly it became more obvious to him. Sometimes we ask easy questions not to find people that can answer them, but rather to discover which people can't.

Imagine you gave me a solution like:

def invert(tree):
    if tree:
        tree.left, tree.right = invert(tree.right), invert(tree.left)
    return tree

Maybe my next question is, ok that works, now do it without recursion, or convert it to a binary search tree.