Hundir incluso Nodes en árbol binario

Dado un árbol binario que tiene elementos pares e impares, sumerja todos sus Nodes con valores pares de modo que ningún Node con un valor par pueda ser padre de un Node con un valor impar. 

Puede haber múltiples salidas para un árbol dado, necesitamos imprimir una de ellas. Siempre es posible convertir un árbol (Tenga en cuenta que un Node con Nodes impares y todos los Nodes pares siguen la regla)

Ejemplos:  

Input: 
       1
     /    \
    5       8
  /  \     /  \
 2    4   9    10
Output: 
1 
5 9 
2 4 8 10

Level order traversal after
sinking all the nodes

Input: 
  4
 /  \
2    1
Output: 
4
2 1

Explanation: 
In the first case
Given tree
       4
    /    \
   2      1

There are two trees possible
       1            1
    /    \   OR   /   \
   2      4      4     2 
  

In the second example also,
Given tree
       1
     /    \
    5       8
  /  \     /  \
 2    4   9    10

There are more than one tree
that can satisfy the condition
      1                 1
   /    \            /    \     
  5       9    OR   5      9   
 /  \    /  \      /  \   / \   
2   4  8   10    4    2  8  10

Acercarse: 

• Básicamente, se requiere intercambiar el valor par de un Node con el valor impar de uno de sus descendientes.
• La idea es atravesar el árbol en orden posterior.
• Dado que procesamos en orden posterior, para cada Node par encontrado, sus subárboles izquierdo y derecho ya están equilibrados (hundidos).
• Compruebe si es un Node par y su hijo izquierdo o derecho tiene un valor impar. Si se encuentra el valor impar, intercambie los datos del Node con los del Node hijo impar y llame al procedimiento en el hijo impar para equilibrar el subárbol.
• Si ambos hijos tienen valores pares, eso significa que todos sus descendientes son pares.

A continuación se muestra la implementación de la idea: 

# Python3 program to sink even nodes
# to the bottom of binary tree
 
# A binary tree node
# Helper function to allocates a new node
class newnode:
 
    # Constructor to create a new node
    def __init__(self, key):
        self.data = key
        self.left = None
        self.right = None
 
# Helper function to check
# if node is leaf node
def isLeaf(root):
    return (root.left == None and
            root.right == None)
 
# A recursive method to sink a tree with even root
# This method assumes that the subtrees are
# already sinked. This method is similar to
# Heapify of Heap-Sort
def sink(root):
     
    # If None or is a leaf, do nothing
    if (root == None or isLeaf(root)):
        return
     
    # if left subtree exists and
    # left child is even
    if (root.left and (root.left.data & 1)):
         
        # swap root's data with left child
        # and fix left subtree
        root.data, root.left.data = root.left.data, root.data
        sink(root.left)
         
    # if right subtree exists and
    # right child is even
    elif(root.right and (root.right.data & 1)):
         
        # swap root's data with right child
        # and fix right subtree
        root.data, root.right.data = root.right.data, root.data
        sink(root.right)
 
# Function to sink all even nodes to
# the bottom of binary tree. It does
# a postorder traversal and calls sink()
# if any even node is found
def sinkevenNodes(root):
     
    # If None or is a leaf, do nothing
    if (root == None or isLeaf(root)):
        return
         
    # Process left and right subtrees
    # before this node
    sinkevenNodes(root.left)
    sinkevenNodes(root.right)
     
    # If root is even, sink it
    if not (root.data & 1):
        sink(root)
 
# Helper function to do Level Order Traversal
# of Binary Tree level by level. This function
# is used here only for showing modified tree.
def printLevelOrder(root):
    q = []
    q.append(root)
     
    # Do Level order traversal
    while (len(q)):
         
        nodeCount = len(q)
         
        # Print one level at a time
        while (nodeCount):
            node = q[0]
            print(node.data, end = " ")
            q.pop(0)
            if (node.left != None):
                q.append(node.left)
            if (node.right != None):
                q.append(node.right)
            nodeCount -= 1
         
        # Line separator for levels
        print()
 
# Driver Code
""" Constructed binary tree is
            1
        / \
        5 8
        / \ / \
    2 4 9 10     """
root = newnode(1)
root.left = newnode(5)
root.right = newnode(8)
root.left.left = newnode(2)
root.left.right = newnode(4)
root.right.left = newnode(9)
root.right.right = newnode(10)
 
sinkevenNodes(root)
 
printLevelOrder(root)
 
# This code is contributed by SHUBHAMSINGH10

<script>
 
 
// Program to sink even nodes
// to the bottom of binary tree
 
// A binary tree node
class Node {
 
    constructor()
    {
        this.data = 0;
        this.left = null;
        this.right = null;
    }
};
 
// Helper function to allocates
// a new node
function newnode(data)
{
    var node = new Node;
    node.data = data;
    return node;
}
 
// Helper function to check
// if node is leaf node
function isLeaf(root)
{
    return (root.left == null
            && root.right == null);
}
 
// A recursive method to sink
// a tree with odd root
 
// This method assumes that the
// subtrees are already sinked.
// This method is similar to
// Heapify of Heap-Sort
function sink(root)
{
    // If null or is a leaf, do nothing
    if (root == null || isLeaf(root))
        return;
 
    // If left subtree exists
    // and left child is odd
    if (root.left
        && (root.left.data & 1)) {
 
        // Swap root's data with left
        // child and fix left subtree
        [root.data,
             root.left.data] = [root.left.data, root.data];
        sink(root.left);
    }
 
    // If right subtree exists
    // and right child is odd
    else if (root.right
             && (root.right.data & 1)) {
 
        // Swap root's data with right
        // child and fix right subtree
        [root.data,
             root.right.data] = [root.right.data, root.data];
        sink(root.right);
    }
}
 
// Function to sink all even
// nodes to the bottom of
// binary tree. It does a
// postorder traversal and
// calls sink()
// if any even node is found
function sinkevenNodes( root)
{
    // If null or is a
    // leaf, do nothing
    if (root == null || isLeaf(root))
        return;
 
    // Process left and right
    // subtrees before this node
    sinkevenNodes(root.left);
    sinkevenNodes(root.right);
 
    // If root is even, sink it
    if (!(root.data & 1))
        sink(root);
}
 
// Helper function to do Level
// Order Traversal of Binary Tree
// level by level. This function
// is used here only for showing
// modified tree.
function printLevelOrder(root)
{
    var q = [];
    q.push(root);
 
    // Do Level order traversal
    while (q.length!=0) {
        var nodeCount = q.length;
 
        // Print one level at a time
        while (nodeCount) {
 
            var node = q[0];
 
            document.write(node.data + " ");
 
            q.shift();
 
            // If the node has a left
            // child then push into queue
            if (node.left != null)
                q.push(node.left);
 
            // If the node has a right
            // child then push into queue
            if (node.right != null)
                q.push(node.right);
 
            nodeCount--;
        }
 
        // Line separator for levels
        document.write("<br>");
    }
}
 
// Driver code
 
    /* Constructed binary tree is
        1
      /  \
     5    8
    / \  / \
   2  4 9  10     */
 
    var root = newnode(1);
    root.left = newnode(5);
    root.right = newnode(8);
    root.left.left = newnode(2);
    root.left.right = newnode(4);
    root.right.left = newnode(9);
    root.right.right = newnode(10);
 
    // Calling function to perform
    // sink operation
    sinkevenNodes(root);
 
    // Printing the updated tree
    // using level order traversal
    printLevelOrder(root);
 
 
 
</script>

1 
5 9 
2 4 8 10