Given a binary tree, print all nodes will are full nodes. Full Nodes are nodes which has both left and right children as non-empty.
Examples:
Input : 10
/
8 2
/ /
3 5 7
Output : 10 8
Input : 1
/
2 3
/
4 6
Output : 1 3
This is a simple problem. We do any of the traversals (Inorder, Preorder, Postorder, level order traversal) and keep printing nodes that have mode left and right children as non-NULL.
C++
// A C++ program to find the all full nodes in // a given binary tree #include <iostream> using namespace std; struct Node { int data; struct Node *left, *right; }; Node *newNode(int data) { Node *temp = new Node; temp->data = data; temp->left = temp->right = NULL; return temp; } // Traverses given tree in Inorder fashion and // prints all nodes that have both children as // non-empty. void findFullNode(Node *root) { if (root != NULL) { findFullNode(root->left); if (root->left != NULL && root->right != NULL) cout << root->data << " "; findFullNode(root->right); } } // Driver program to test above function int main() { Node* root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->right->left = newNode(5); root->right->right = newNode(6); root->right->left->right = newNode(7); root->right->right->right = newNode(8); root->right->left->right->left = newNode(9); findFullNode(root); return 0; } |
Java
// Java program to find the all full nodes in // a given binary tree public class FullNodes { // Traverses given tree in Inorder fashion and // prints all nodes that have both children as // non-empty. public static void findFullNode(Node root) { if (root != null) { findFullNode(root.left); if (root.left != null && root.right != null) System.out.print(root.data+" "); findFullNode(root.right); } } public static void main(String args[]) { Node root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.right.left = new Node(5); root.right.right = new Node(6); root.right.left.right = new Node(7); root.right.right.right = new Node(8); root.right.left.right.left = new Node(9); findFullNode(root); } } /* A binary tree node */class Node { int data; Node left, right; Node(int data) { left=right=null; this.data=data; } }; //This code is contributed by Gaurav Tiwari |
Python3
# Python3 program to find the all # full nodes in a given binary tree # Binary Tree Node """ utility that allocates a newNode with the given key """class newNode: # Construct to create a newNode def __init__(self, key): self.data = key self.left = None self.right = None # Traverses given tree in Inorder # fashion and prints all nodes that # have both children as non-empty. def findFullNode(root) : if (root != None) : findFullNode(root.left) if (root.left != None and root.right != None) : print(root.data, end = " ") findFullNode(root.right) # Driver Code if __name__ == '__main__': root = newNode(1) root.left = newNode(2) root.right = newNode(3) root.left.left = newNode(4) root.right.left = newNode(5) root.right.right = newNode(6) root.right.left.right = newNode(7) root.right.right.right = newNode(8) root.right.left.right.left = newNode(9) findFullNode(root) # This code is contributed by # Shubham Singh(SHUBHAMSINGH10) |
C#
// C# program to find the all full nodes in // a given binary tree using System; public class FullNodes { // Traverses given tree in Inorder fashion and // prints all nodes that have both children as // non-empty. static void findFullNode(Node root) { if (root != null) { findFullNode(root.left); if (root.left != null && root.right != null) Console.Write(root.data + " "); findFullNode(root.right); } } public static void Main(String []args) { Node root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.right.left = new Node(5); root.right.right = new Node(6); root.right.left.right = new Node(7); root.right.right.right = new Node(8); root.right.left.right.left = new Node(9); findFullNode(root); } } /* A binary tree node */class Node { public int data; public Node left, right; public Node(int data) { left = right = null; this.data = data; } }; // This code is contributed by 29AjayKumar |
Output:
1 3
Time Complexity : O(n)
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