Factor Tree of a given Number
Factor Tree is an intuitive method to understand the factors of a number. It shows how all the factors are been derived from the number. It is a special diagram where you find the factors of a number, then the factors of those numbers, etc until you can’t factor anymore. The ends are all the prime factors of the original number.
Example:
Input : v = 48 Output : Root of below tree 48 /\ 2 24 /\ 2 12 /\ 2 6 /\ 2 3
The factor tree is created recursively. A binary tree is used.
- We start with a number and find the minimum divisor possible.
- Then, we divide the parent number by the minimum divisor.
- We store both the divisor and quotient as two children of the parent number.
- Both the children are sent into function recursively.
- If a divisor less than half the number is not found, two children are stored as NULL.
Implementation:
C++
// C++ program to construct Factor Tree for // a given number #include<bits/stdc++.h> using namespace std; // Tree node struct Node { struct Node *left, *right; int key; }; // Utility function to create a new tree Node Node* newNode( int key) { Node* temp = new Node; temp->key = key; temp->left = temp->right = NULL; return temp; } // Constructs factor tree for given value and stores // root of tree at given reference. void createFactorTree( struct Node **node_ref, int v) { (*node_ref) = newNode(v); // the number is factorized for ( int i = 2 ; i < v/2 ; i++) { if (v % i != 0) continue ; // If we found a factor, we construct left // and right subtrees and return. Since we // traverse factors starting from smaller // to greater, left child will always have // smaller factor createFactorTree(&((*node_ref)->left), i); createFactorTree(&((*node_ref)->right), v/i); return ; } } // Iterative method to find the height of Binary Tree void printLevelOrder(Node *root) { // Base Case if (root == NULL) return ; queue<Node *> q; q.push(root); while (q.empty() == false ) { // Print front of queue and remove // it from queue Node *node = q.front(); cout << node->key << " " ; q.pop(); if (node->left != NULL) q.push(node->left); if (node->right != NULL) q.push(node->right); } } // driver program int main() { int val = 48; // sample value struct Node *root = NULL; createFactorTree(&root, val); cout << "Level order traversal of " "constructed factor tree" ; printLevelOrder(root); return 0; } |
Java
// Java program to construct Factor Tree for // a given number import java.util.*; class GFG { // Tree node static class Node { Node left, right; int key; }; static Node root; // Utility function to create a new tree Node static Node newNode( int key) { Node temp = new Node(); temp.key = key; temp.left = temp.right = null ; return temp; } // Constructs factor tree for given value and stores // root of tree at given reference. static Node createFactorTree(Node node_ref, int v) { (node_ref) = newNode(v); // the number is factorized for ( int i = 2 ; i < v/ 2 ; i++) { if (v % i != 0 ) continue ; // If we found a factor, we construct left // and right subtrees and return. Since we // traverse factors starting from smaller // to greater, left child will always have // smaller factor node_ref.left = createFactorTree(((node_ref).left), i); node_ref.right = createFactorTree(((node_ref).right), v/i); return node_ref; } return node_ref; } // Iterative method to find the height of Binary Tree static void printLevelOrder(Node root) { // Base Case if (root == null ) return ; Queue<Node > q = new LinkedList<>(); q.add(root); while (q.isEmpty() == false ) { // Print front of queue and remove // it from queue Node node = q.peek(); System.out.print(node.key + " " ); q.remove(); if (node.left != null ) q.add(node.left); if (node.right != null ) q.add(node.right); } } // Driver program public static void main(String[] args) { int val = 48 ; // sample value root = null ; root = createFactorTree(root, val); System.out.println( "Level order traversal of " + "constructed factor tree" ); printLevelOrder(root); } } // This code is contributed by Rajput-Ji |
Python3
# Python program to construct Factor Tree for # a given number class Node: def __init__( self , key): self .left = None self .right = None self .key = key # Utility function to create a new tree Node def newNode(key): temp = Node(key) return temp # Constructs factor tree for given value and stores # root of tree at given reference. def createFactorTree(node_ref, v): node_ref = newNode(v) # the number is factorized for i in range ( 2 , int (v / 2 )): if (v % i ! = 0 ): continue # If we found a factor, we construct left # and right subtrees and return. Since we # traverse factors starting from smaller # to greater, left child will always have # smaller factor node_ref.left = createFactorTree(((node_ref).left), i) node_ref.right = createFactorTree(((node_ref).right), int (v / i)) return node_ref return node_ref # Iterative method to find the height of Binary Tree def printLevelOrder(root): # Base Case if (root = = None ): return q = []; q.append(root); while ( len (q) > 0 ): # Print front of queue and remove # it from queue node = q[ 0 ] print (node.key, end = " " ) q = q[ 1 :] if (node.left ! = None ): q.append(node.left) if (node.right ! = None ): q.append(node.right) val = 48 # sample value root = None root = createFactorTree(root, val) print ( "Level order traversal of constructed factor tree" ) printLevelOrder(root) # This code is contributed by shinjanpatra |
C#
// C# program to construct Factor Tree for // a given number using System; using System.Collections.Generic; public class GFG { // Tree node public class Node { public Node left, right; public int key; }; static Node root; // Utility function to create a new tree Node static Node newNode( int key) { Node temp = new Node(); temp.key = key; temp.left = temp.right = null ; return temp; } // Constructs factor tree for given value and stores // root of tree at given reference. static Node createFactorTree(Node node_ref, int v) { (node_ref) = newNode(v); // the number is factorized for ( int i = 2 ; i < v/2 ; i++) { if (v % i != 0) continue ; // If we found a factor, we construct left // and right subtrees and return. Since we // traverse factors starting from smaller // to greater, left child will always have // smaller factor node_ref.left = createFactorTree(((node_ref).left), i); node_ref.right = createFactorTree(((node_ref).right), v/i); return node_ref; } return node_ref; } // Iterative method to find the height of Binary Tree static void printLevelOrder(Node root) { // Base Case if (root == null ) return ; Queue<Node > q = new Queue<Node>(); q.Enqueue(root); while (q.Count != 0) { // Print front of queue and remove // it from queue Node node = q.Peek(); Console.Write(node.key + " " ); q.Dequeue(); if (node.left != null ) q.Enqueue(node.left); if (node.right != null ) q.Enqueue(node.right); } } // Driver program public static void Main(String[] args) { int val = 48; // sample value root = null ; root = createFactorTree(root, val); Console.WriteLine( "Level order traversal of " + "constructed factor tree" ); printLevelOrder(root); } } // This code is contributed by gauravrajput1 |
Javascript
<script> // Javascript program to construct Factor Tree for // a given number class Node { constructor(key) { this .left = null ; this .right = null ; this .key = key; } } let root; // Utility function to create a new tree Node function newNode(key) { let temp = new Node(key); return temp; } // Constructs factor tree for given value and stores // root of tree at given reference. function createFactorTree(node_ref, v) { (node_ref) = newNode(v); // the number is factorized for (let i = 2 ; i < parseInt(v/2, 10) ; i++) { if (v % i != 0) continue ; // If we found a factor, we construct left // and right subtrees and return. Since we // traverse factors starting from smaller // to greater, left child will always have // smaller factor node_ref.left = createFactorTree(((node_ref).left), i); node_ref.right = createFactorTree(((node_ref).right), parseInt(v/i, 10)); return node_ref; } return node_ref; } // Iterative method to find the height of Binary Tree function printLevelOrder(root) { // Base Case if (root == null ) return ; let q = []; q.push(root); while (q.length > 0) { // Print front of queue and remove // it from queue let node = q[0]; document.write(node.key + " " ); q.shift(); if (node.left != null ) q.push(node.left); if (node.right != null ) q.push(node.right); } } let val = 48; // sample value root = null ; root = createFactorTree(root, val); document.write( "Level order traversal of " + "constructed factor tree" + "</br>" ); printLevelOrder(root); // This code is contributed by suresh07. </script> |
Output
Level order traversal of constructed factor tree48 2 24 2 12 2 6 2 3
Time Complexity: O(n), where n is the given number.
Space Complexity: O(k), where k is the factor of the number.