Binary Tree - Most elegant way to traverse from the last level to root

Question

I am looking for an implementation that allows me to traverse through a Binary Search tree, starting from the last level from left to right to the root, e.g.:

                 A
               B   C
             D  E    G

Should return: [D, E, G, B, C, A]. I am interested in both, a recursive approach or an iterative approach.

Answer 1

I'm not sure whether my solution in Python is elegant enough, but maybe it will be helpful, nevertheless.

Introduction

Let's consider an example as follows:

                   8
                 /   \
                5    10
               / \     \  
              4   6    12

The expected output is 4, 6, 12, 5, 10, 8. But how to achieve this?

Step 1 - BFS

Let's do a BFS with a slight modification - first traverse a right child, and then a left one.

def bfs(node):
    q  = []
    q.append(node)
    while q:
        current = q.pop(0)
        print (current.value, end = ' ')
        if current.right:
            q.append(current.right)
        if current.left:
            q.append(current.left)

The output is as follows:

8, 10, 5, 12, 6, 4

The output is basically a reverse of the expected output!

Step 2 - Reverse BFS output

To do this, introduce a stack variable that saves the current element of the queue.

def bfsFromBottomToTop(node):
    q  = []
    q.append(node)
    st = [] # create a stack variable
    while q:
        current = q.pop(0)
        st.append(current.value) # push the current element to the stack
        if current.right:
            q.append(current.right)
        if current.left:
            q.append(current.left)

Then, you can pop all elements off the stack at the end of the method as below:

    ...
    while st:
        print(st.pop(), end = ' ')
    ...

4 6 12 5 10 8

Full Code

Here's the full code that can be used for trying it out yourself.

class Node:
    def __init__(self, value):
        self.left = None
        self.right = None
        self.value = value

def insert(node, value):
    if node is None:
        return Node(value)

    if node.value > value:
        node.left = insert(node.left, value)
    else:
        node.right = insert(node.right, value)

    return node

def bfsFromBottomToTop(node):
    q  = []
    q.append(node)
    st = []
    while q:
        current = q.pop(0)
        st.append(current.value)
        if current.right:
            q.append(current.right)
        if current.left:
            q.append(current.left)

    while st:
        print(st.pop(), end = ' ')

root = Node(8)
insert(root, 5)
insert(root, 10)
insert(root, 6)
insert(root, 4)
insert(root, 12)
bfsFromBottomToTop(root)