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.
Consider the following binary tree.
All right nodes in the tree are leaf nodes and have a sibling. The corresponding upside down tree is the following.
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.
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.
Output is terminated by an EOF character.
Here is a Ruby implementation.
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 month. Did I mention that I love to answer questions?