A popular problem associated with Leetcode’s online judge. You are given binary trees of a very particular form and you are asked to flip them upside down. A problem not too easy and not too hard.

Problem

Consider the following binary tree.

    1
/ \
2 3
/ \
4 5

All right nodes in the tree are leaf nodes and have a sibling. The corresponding upside down tree is the following.

   4
/ \
5 2
/ \
3 1

In the upside down tree, the original right nodes are left nodes and all left nodes are leaf nodes.

Input. The first line of input indicates the root node. Each subsequent line indicates a parent and its two children. Each line consists of three integers separated by one space. The first number is a parent node, the second is the left child of the parent, and the third number is the right node. When a child does not exist, the corresponding integer is -1. For example, the following input corresponds to the original tree.

1
1 2 3
2 4 5

Input is terminated by an EOF character. All trees are such that all right nodes are leaf nodes and have a sibling.

Output. The first line of input indicates the root of the upside down tree. Each line of output consists of three integers separated by one space and indicate a parent and its two children like in the input. For example, the following input corresponds to the upside down tree.

4
2 3 1
4 5 2

Output is terminated by an EOF character.

Solution

Here is a Ruby implementation.

def flip r, pp
nr = r
npp = {}
while !!pp[r]
nr = pp[r][0]
npp[nr] = [pp[r][1], r]
r = nr
end
return nr, npp
end

def main
pp = {}
r = readline.strip rescue return
while true
i = readline.strip.split ' ' rescue break
pp[i[0]] = i[1..2]
end
nr, npp = flip r, pp
puts nr
npp.each { |k, v| puts "#{k} #{v[0]} #{v[1]}" }
end

main

Want to read more?

I love to explain and answer questions on programming problems, the kind you find in coding interviews. I publish a new programming problem and its solution every Sunday. Did I mention that I love to answer questions?

If you would like to get the latest problem + solution, subscribe to the newsletter or subscribe via RSS. You can also follow me on Twitter, GitHub, and LinkedIn.

Comments