Given a binary tree and a node, print all cousins of given node. Note that siblings should not be printed.
Example:
Input : root of below tree
1
/
2 3
/ /
4 5 6 7
and pointer to a node say 5.
Output : 6, 7
The idea to first find level of given node using the approach discussed here. Once we have found level, we can print all nodes at a given level using the approach discussed here. The only thing to take care of is, sibling should not be printed. To handle this, we change the printing function to first check for sibling and print node only if it is not sibling.
Below is the implementation of above idea.
C++
// C++ program to print cousins of a node #include <bits/stdc++.h> using namespace std; // A Binary Tree Node struct Node { int data; Node *left, *right; }; // A utility function to create a new // Binary Tree Node Node *newNode(int item) { Node *temp = new Node; temp->data = item; temp->left = temp->right = NULL; return temp; } /* It returns level of the node if it is present in tree, otherwise returns 0.*/int getLevel(Node *root, Node *node, int level) { // base cases if (root == NULL) return 0; if (root == node) return level; // If node is present in left subtree int downlevel = getLevel(root->left, node, level + 1); if (downlevel != 0) return downlevel; // If node is not present in left subtree return getLevel(root->right, node, level + 1); } /* Print nodes at a given level such that sibling of node is not printed if it exists */void printGivenLevel(Node* root, Node *node, int level) { // Base cases if (root == NULL || level < 2) return; // If current node is parent of a node // with given level if (level == 2) { if (root->left == node || root->right == node) return; if (root->left) cout << root->left->data << " "; if (root->right) cout << root->right->data; } // Recur for left and right subtrees else if (level > 2) { printGivenLevel(root->left, node, level - 1); printGivenLevel(root->right, node, level - 1); } } // This function prints cousins of a given node void printCousins(Node *root, Node *node) { // Get level of given node int level = getLevel(root, node, 1); // Print nodes of given level. printGivenLevel(root, node, level); } // Driver Code int main() { Node *root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); root->left->right->right = newNode(15); root->right->left = newNode(6); root->right->right = newNode(7); root->right->left->right = newNode(8); printCousins(root, root->left->right); return 0; } // This code is contributed // by Akanksha Rai |
C
// C program to print cousins of a node #include <stdio.h> #include <stdlib.h> // A Binary Tree Node struct Node { int data; Node *left, *right; }; // A utility function to create a new Binary // Tree Node Node *newNode(int item) { Node *temp = new Node; temp->data = item; temp->left = temp->right = NULL; return temp; } /* It returns level of the node if it is present in tree, otherwise returns 0.*/int getLevel(Node *root, Node *node, int level) { // base cases if (root == NULL) return 0; if (root == node) return level; // If node is present in left subtree int downlevel = getLevel(root->left, node, level+1); if (downlevel != 0) return downlevel; // If node is not present in left subtree return getLevel(root->right, node, level+1); } /* Print nodes at a given level such that sibling of node is not printed if it exists */void printGivenLevel(Node* root, Node *node, int level) { // Base cases if (root == NULL || level < 2) return; // If current node is parent of a node with // given level if (level == 2) { if (root->left == node || root->right == node) return; if (root->left) printf("%d ", root->left->data); if (root->right) printf("%d ", root->right->data); } // Recur for left and right subtrees else if (level > 2) { printGivenLevel(root->left, node, level-1); printGivenLevel(root->right, node, level-1); } } // This function prints cousins of a given node void printCousins(Node *root, Node *node) { // Get level of given node int level = getLevel(root, node, 1); // Print nodes of given level. printGivenLevel(root, node, level); } // Driver Program to test above functions int main() { Node *root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); root->left->right->right = newNode(15); root->right->left = newNode(6); root->right->right = newNode(7); root->right->left->right = newNode(8); printCousins(root, root->left->right); return 0; } |
Java
// Java program to print cousins of a node class GfG { // A Binary Tree Node static class Node { int data; Node left, right; } // A utility function to create a new Binary // Tree Node static Node newNode(int item) { Node temp = new Node(); temp.data = item; temp.left = null; temp.right = null; return temp; } /* It returns level of the node if it is present in tree, otherwise returns 0.*/static int getLevel(Node root, Node node, int level) { // base cases if (root == null) return 0; if (root == node) return level; // If node is present in left subtree int downlevel = getLevel(root.left, node, level+1); if (downlevel != 0) return downlevel; // If node is not present in left subtree return getLevel(root.right, node, level+1); } /* Print nodes at a given level such that sibling of node is not printed if it exists */static void printGivenLevel(Node root, Node node, int level) { // Base cases if (root == null || level < 2) return; // If current node is parent of a node with // given level if (level == 2) { if (root.left == node || root.right == node) return; if (root.left != null) System.out.print(root.left.data + " "); if (root.right != null) System.out.print(root.right.data + " "); } // Recur for left and right subtrees else if (level > 2) { printGivenLevel(root.left, node, level-1); printGivenLevel(root.right, node, level-1); } } // This function prints cousins of a given node static void printCousins(Node root, Node node) { // Get level of given node int level = getLevel(root, node, 1); // Print nodes of given level. printGivenLevel(root, node, level); } // Driver Program to test above functions public static void main(String[] args) { Node root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(5); root.left.right.right = newNode(15); root.right.left = newNode(6); root.right.right = newNode(7); root.right.left.right = newNode(8); printCousins(root, root.left.right); } } |
Python3
# Python3 program to print cousins of a node # A utility function to create a new # Binary Tree Node class newNode: def __init__(self, item): self.data = item self.left = self.right = None # It returns level of the node if it is # present in tree, otherwise returns 0. def getLevel(root, node, level): # base cases if (root == None): return 0 if (root == node): return level # If node is present in left subtree downlevel = getLevel(root.left, node, level + 1) if (downlevel != 0): return downlevel # If node is not present in left subtree return getLevel(root.right, node, level + 1) # Prnodes at a given level such that # sibling of node is not printed if # it exists def printGivenLevel(root, node, level): # Base cases if (root == None or level < 2): return # If current node is parent of a # node with given level if (level == 2): if (root.left == node or root.right == node): return if (root.left): print(root.left.data, end = " ") if (root.right): print(root.right.data, end = " ") # Recur for left and right subtrees elif (level > 2): printGivenLevel(root.left, node, level - 1) printGivenLevel(root.right, node, level - 1) # This function prints cousins of a given node def printCousins(root, node): # Get level of given node level = getLevel(root, node, 1) # Prnodes of given level. printGivenLevel(root, node, level) # Driver Code if __name__ == '__main__': root = newNode(1) root.left = newNode(2) root.right = newNode(3) root.left.left = newNode(4) root.left.right = newNode(5) root.left.right.right = newNode(15) root.right.left = newNode(6) root.right.right = newNode(7) root.right.left.right = newNode(8) printCousins(root, root.left.right) # This code is contributed by PranchalK |
C#
// C# program to print cousins of a node using System; public class GfG { // A Binary Tree Node class Node { public int data; public Node left, right; } // A utility function to create // a new Binary Tree Node static Node newNode(int item) { Node temp = new Node(); temp.data = item; temp.left = null; temp.right = null; return temp; } /* It returns level of the node if it is present in tree, otherwise returns 0.*/static int getLevel(Node root, Node node, int level) { // base cases if (root == null) return 0; if (root == node) return level; // If node is present in left subtree int downlevel = getLevel(root.left, node, level + 1); if (downlevel != 0) return downlevel; // If node is not present in left subtree return getLevel(root.right, node, level + 1); } /* Print nodes at a given level such that sibling of node is not printed if it exists */static void printGivenLevel(Node root, Node node, int level) { // Base cases if (root == null || level < 2) return; // If current node is parent of a node with // given level if (level == 2) { if (root.left == node || root.right == node) return; if (root.left != null) Console.Write(root.left.data + " "); if (root.right != null) Console.Write(root.right.data + " "); } // Recur for left and right subtrees else if (level > 2) { printGivenLevel(root.left, node, level - 1); printGivenLevel(root.right, node, level - 1); } } // This function prints cousins of a given node static void printCousins(Node root, Node node) { // Get level of given node int level = getLevel(root, node, 1); // Print nodes of given level. printGivenLevel(root, node, level); } // Driver code public static void Main(String[] args) { Node root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(5); root.left.right.right = newNode(15); root.right.left = newNode(6); root.right.right = newNode(7); root.right.left.right = newNode(8); printCousins(root, root.left.right); } } // This code is contributed Rajput-Ji |
Output :
6 7
Time Complexity : O(n)
Can we solve this problem using single traversal? Please refer below article
Print cousins of a given node in Binary Tree | Single Traversal
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above
leave a comment
0 Comments