Sink Odd nodes in Binary Tree

0 0 10 minutes read

Given a Binary Tree having odd and even elements, sink all its odd valued nodes such that no node with odd value could be parent of node with even value. There can be multiple outputs for a given tree, we need to print one of them. It is always possible to convert a tree (Note that a node with even nodes and all odd nodes follows the rule)

Input : 
       1
    /    \
   2      3
Output
       2            2
    /    \   OR   /   \
   1      3      3     1 
  

Input : 
       1
     /    \
    5       8
  /  \     /  \
 2    4   9    10
Output :
    2                 4
  /    \            /    \     
 4       8    OR   2      8    OR .. (any tree with 
/  \    /  \      /  \   / \          same keys and 
5   1  9   10    5    1 9   10        no odd is parent
                                      of even)

We strongly recommend you to minimize your browser and try this yourself first.

Basically, we need to swap odd value of a node with even value of one of its descendants. The idea is to traverse the tree in a postorder fashion. Since we process in postorder, for each odd node encountered, its left and right subtrees are already balanced (sinked), we check if it’s an odd node and its left or right child has an even value. If even value is found, we swap the node’s data with that of even child node and call the procedure on the even child to balance the subtree. If both children have odd values, that means that all its descendants are odd.
Below is the implementation of the idea.

Implementation:

C++

// Program to sink odd nodes to the bottom of
// binary tree
#include<bits/stdc++.h>
using namespace std;
 
// A binary tree node
struct Node
{
    int data;
    Node* left, *right;
};
 
// Helper function to allocates a new node
Node* newnode(int data)
{
    Node* node = new Node;
    node->data = data;
    node->left = node->right = NULL;
    return node;
}
 
// Helper function to check if node is leaf node
bool isLeaf(Node *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
void sink(Node *&root)
{
    // If NULL or is a leaf, do nothing
    if (root == NULL || isLeaf(root))
        return;
 
    // if left subtree exists and left child is even
    if (root->left && !(root->left->data & 1))
    {
        // swap root's data with left child and
        // fix left subtree
        swap(root->data, root->left->data);
        sink(root->left);
    }
 
    // if right subtree exists and right child is even
    else if(root->right && !(root->right->data & 1))
    {
        // swap root's data with right child and
        // fix right subtree
        swap(root->data, root->right->data);
        sink(root->right);
    }
}
 
// Function to sink all odd nodes to the bottom of binary
// tree. It does a postorder traversal and calls sink()
// if any odd node is found
void sinkOddNodes(Node* &root)
{
    // If NULL or is a leaf, do nothing
    if (root == NULL || isLeaf(root))
        return;
 
    // Process left and right subtrees before this node
    sinkOddNodes(root->left);
    sinkOddNodes(root->right);
 
    // If root is odd, 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.
void printLevelOrder(Node* root)
{
    queue<Node*> q;
    q.push(root);
 
    // Do Level order traversal
    while (!q.empty())
    {
        int nodeCount = q.size();
 
        // Print one level at a time
        while (nodeCount)
        {
            Node *node = q.front();
            printf("%d ", node->data);
            q.pop();
            if (node->left != NULL)
                q.push(node->left);
            if (node->right != NULL)
                q.push(node->right);
            nodeCount--;
        }
 
        // Line separator for levels
        printf("\n");
    }
}
 
// Driver program to test above functions
int main()
{
    /* Constructed binary tree is
            1
          /   \
         5      8
        / \   /  \
       2   4 9   10     */
 
    Node *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);
 
    sinkOddNodes(root);
 
    printf("Level order traversal of modified tree\n");
    printLevelOrder(root);
 
    return 0;
}

Java

// Java program to sink odd nodes to the bottom of
// binary tree
import java.util.*;
 
class GFG
{
    // A binary tree node
    static class Node
    {
        int data;
        Node left, right;
    };
     
    // returns a new tree Node
    static Node newnode(int data)
    {
        Node temp = new Node();
        temp.data = data;
        temp.left = temp.right = null;
        return temp;
    }
     
    // Helper function to check if node is leaf node
    static boolean isLeaf(Node root)
    {
        if(root==null){
            return false;
        }
        return (root.left == null && root.right == null)?true:false;
    }
      
    // 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
    static void sink(Node root)
    {
        // If NULL or is a leaf, do nothing
        if (root == null || isLeaf(null))
            return;
      
        // if left subtree exists and left child is even
        if (root.left!=null && (root.left.data & 1)==0)
        {
            // swap root's data with left child and
            // fix left subtree
            int temp = root.data;
            root.data=root.left.data;
            root.left.data=temp;
            sink(root.left);
        }
      
        // if right subtree exists and right child is even
        else if(root.right!=null && (root.right.data & 1)==0)
        {
            // swap root's data with right child and
            // fix right subtree
            int temp = root.data;
            root.data=root.right.data;
            root.right.data=temp;
            sink(root.right);
        }
    }
      
    // Function to sink all odd nodes to the bottom of binary
    // tree. It does a postorder traversal and calls sink()
    // if any odd node is found
    static void sinkOddNodes(Node root)
    {
        // If NULL or is a leaf, do nothing
        if (root == null || isLeaf(root))
            return;
      
        // Process left and right subtrees before this node
        sinkOddNodes(root.left);
        sinkOddNodes(root.right);
      
        // If root is odd, sink it
        if ((root.data & 1)!=0)
             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.
    static void printLevelOrder(Node root)
    {
        Queue<Node> q = new LinkedList<>();
        q.add(root);
      
        // Do Level order traversal
        while (!q.isEmpty())
        {
            int nodeCount = q.size();
      
            // Print one level at a time
            while (nodeCount>0)
            {
                Node node = q.poll();
                System.out.print(node.data+" ");
                if (node.left != null)
                    q.add(node.left);
                if (node.right != null)
                    q.add(node.right);
                nodeCount--;
            }
      
            // Line separator for levels
            System.out.println("");
        }
    }
     
    // Driver code
    public static void main(String[] args)
    {
         
        /* Constructed binary tree is
                1
              /   \
             5      8
            / \   /  \
           2   4 9   10     */
      
        Node 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);
         
        sinkOddNodes(root);
  
        System.out.print("Level order traversal of modified tree\n");
        printLevelOrder(root);
    }
}
 
/* This code is contributed by shruti456rawal */

Python3

# Python3 program to sink odd 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 odd 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 not(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 
    else if(root.right and not(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 odd nodes to 
# the bottom of binary tree. It does 
# a postorder traversal and calls sink() 
# if any odd node is found 
def sinkOddNodes(root):
     
    # If None or is a leaf, do nothing 
    if (root == None or isLeaf(root)):
        return
         
    # Process left and right subtrees 
    # before this node 
    sinkOddNodes(root.left) 
    sinkOddNodes(root.right) 
     
    # If root is odd, 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. 
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) 
 
sinkOddNodes(root) 
 
print("Level order traversal of modified tree") 
printLevelOrder(root)
 
# This code is contributed by SHUBHAMSINGH10

C#

using System;
using System.Collections.Generic;
 
class GFG {
    // A binary tree node
    class Node {
        public int data;
        public Node left, right;
    };
 
    // returns a new tree Node
    static Node newNode(int data)
    {
        Node temp = new Node();
        temp.data = data;
        temp.left = temp.right = null;
        return temp;
    }
 
    // Helper function to check if node is leaf node
    static bool isLeaf(Node root)
    {
        if (root == null) {
            return false;
        }
        return (root.left == null && root.right == null)
            ? true
            : false;
    }
 
    // 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
    static void sink(Node root)
    {
        // If NULL or is a leaf, do nothing
        if (root == null || isLeaf(null))
            return;
 
        // if left subtree exists and left child is even
        if (root.left != null
            && (root.left.data & 1) == 0) {
            // swap root's data with left child and
            // fix left subtree
            int temp = root.data;
            root.data = root.left.data;
            root.left.data = temp;
            sink(root.left);
        }
 
        // if right subtree exists and right child is even
        else if (root.right != null
                 && (root.right.data & 1) == 0) {
            // swap root's data with right child and
            // fix right subtree
            int temp = root.data;
            root.data = root.right.data;
            root.right.data = temp;
            sink(root.right);
        }
    }
 
    // Function to sink all odd nodes to the bottom of
    // binary tree. It does a postorder traversal and calls
    // sink() if any odd node is found
    static void sinkOddNodes(Node root)
    {
        // If NULL or is a leaf, do nothing
        if (root == null || isLeaf(root))
            return;
 
        // Process left and right subtrees before this node
        sinkOddNodes(root.left);
        sinkOddNodes(root.right);
 
        // If root is odd, sink it
        if ((root.data & 1) != 0)
            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.
    static void printLevelOrder(Node root)
    {
        Queue<Node> q = new Queue<Node>();
        q.Enqueue(root);
 
        // Do Level order traversal
        while (q.Count != 0) {
            int nodeCount = q.Count;
 
            while (nodeCount > 0) {
                Node node = q.Dequeue();
                Console.Write(node.data + " ");
                if (node.left != null)
                    q.Enqueue(node.left);
                if (node.right != null)
                    q.Enqueue(node.right);
                nodeCount--;
            }
 
            Console.WriteLine("");
        }
    }
    static void Main(string[] args)
    {
        /* Constructed binary tree is
                1
              /   \
             5      8
            / \   /  \
           2   4 9   10     */
 
        Node 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);
 
        sinkOddNodes(root);
 
        Console.WriteLine(
            "Level order traversal of modified tree");
        printLevelOrder(root);
    }
}

Javascript

<script>
class Node {
    constructor(data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}
 
// 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 None or is a leaf, do nothing 
    if (root === null || isLeaf(root)) {
        return;
    }
 
    // if left subtree exists and 
    // left child is even 
    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 even 
    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 odd nodes to 
// the bottom of binary tree. It does 
// a postorder traversal and calls sink() 
// if any odd node is found 
function sinkOddNodes(root) {
    // If None or is a leaf, do nothing 
    if (root === null || isLeaf(root)) {
        return;
    }
 
    // Process left and right subtrees 
    // before this node 
    sinkOddNodes(root.left);
    sinkOddNodes(root.right);
 
    // If root is odd, 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) {
    let q = [];
    
q.push(root);
// Do Level order traversal 
while (q.length) {
    let nodeCount = q.length;
 
    // Print one level at a time 
    while (nodeCount) {
        let node = q[0];
        document.write(node.data+ " ");
        q.shift();
        if (node.left !== null) {
            q.push(node.left);
        }
        if (node.right !== null) {
            q.push(node.right);
        }
        nodeCount -= 1;
    }
 
    // Line separator for levels 
    document.write("<br>")
}
}
 
// Driver Code
/* Constructed binary tree is
1
/ \
5 8
/ \ / \
2 4 9 10 */
let root = new Node(1);
root.left = new Node(5);
root.right = new Node(8);
root.left.left = new Node(2);
root.left.right = new Node(4);
root.right.left = new Node(9);
root.right.right = new Node(10);
 
sinkOddNodes(root);
 
document.write("Level order traversal of modified tree");
document.write("<br>")
printLevelOrder(root);
</script>

Output

Level order traversal of modified tree
2 
4 8 
5 1 9 10

Time Complexity:O(N), where N is total number of nodes in binary tree.

Space Complexity: O(N), where N is total number of nodes in binary tree

This article is contributed by Aditya Goel. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!