Paths of Triangular Number in a Binary Tree
Given a Binary Tree, the task is to output the Count of the number of paths formed by only a Triangular number. Xth Triangular number is the sum of the first X natural numbers. Example: {1, 3, 6, 10 . . .} are triangular numbers.
Note: Path should be from root to node.
Examples:
Input:
Output: 1
Explanation: The path formed by only Triangular numbers is {1 → 3 → 6 → 10}.
Input:
Output: 2
Explanation: There are 2 paths formed by only Triangular number which are {1 → 3 → 6} and {1 → 3 → 6 → 10}.
Approach: Implement the idea below to solve the problem
The idea to solve this problem is to generate a sequence of Triangular numbers based on the height of the tree and then traversing the tree in a Preorder traversal to identify paths that match this sequence.
Follow the steps to solve the problem:
- Calculates the height of the tree recursively.
- Initializes the Triangular number sequence based on the height of the tree to count the paths satisfying the condition.
- In Preorder traversal, If the current node is NULL or if the node’s value does not match the triangular number at the current node, then:
- Return the current count as it is.
- If it is a leaf node
- Increment the count of paths.
- Recursively call for the left and right subtree with the updated count.
- After all-recursive call, the value of Count is number of triangular number paths for a given binary tree.
Below is the code to implement the above approach:
C++14
// C++ Code to implement the approach #include <bits/stdc++.h> using namespace std; // Build tree class class Node { public : int data; Node* left; Node* right; Node( int val) { data = val; left = NULL; right = NULL; } }; // Function to find the height // of the given tree int getHeight(Node* root) { // Base case: if the root is // NULL, the height is 0 if (root == NULL) return 0; // Recursive calls to find height of // left and right subtrees int leftHeight = getHeight(root->left); int rightHeight = getHeight(root->right); // Return the maximum height between left // and right subtrees + 1 for the current node return 1 + max(leftHeight, rightHeight); } // Function to count paths in the tree where // node values form a triangular number sequence int cntTriPath(Node* root, int ind, vector< int >& triNum, int count) { // Base case: // If the current node is NULL or its value // does not match the triangular number at index 'ind' if (root == NULL || !(triNum[ind] == root->data)) { return count; // Return the current count } // Check if the current node is a leaf node if (root->left == NULL && root->right == NULL) { // Increment count as it forms a valid path count++; } // Recursive call to explore left // subtree and right subtree count = cntTriPath(root->left, ind + 1, triNum, count); return cntTriPath(root->right, ind + 1, triNum, count); } // Function to count paths in the tree where // node values form a triangular number sequence int CountTriangularNumberPath(Node* root) { // Get the height of the tree int n = getHeight(root); vector< int > triNum; int current_level = 1; int triangular_number = 0; // Generating the triangular number sequence // based on tree height for ( int i = 1; i <= n; i++) { // Add the current level to the // triangular number triangular_number += current_level; triNum.push_back(triangular_number); // Incrementing current level current_level++; } // Call the function to count paths satisfying // the triangular number sequence condition int cntPath = cntTriPath(root, 0, triNum, 0); return cntPath; } // Driver code int main() { // Example tree creation Node* root = new Node(1); root->left = new Node(3); root->right = new Node(3); root->left->left = new Node(2); root->left->right = new Node(5); root->right->left = new Node(6); root->right->right = new Node(7); root->right->left->right = new Node(10); // Finding number of paths and // printing the result int ans = CountTriangularNumberPath(root); cout << ans; return 0; } |
Java
// Java program for the above approach import java.util.ArrayList; import java.util.List; // Build tree class class Node { public int data; public Node left; public Node right; public Node( int val) { data = val; left = null ; right = null ; } } public class GFG { // Function to find the height of the given tree static int getHeight(Node root) { // Base case: if the root is NULL, the height is 0 if (root == null ) return 0 ; // Recursive calls to find height of left and right // subtrees int leftHeight = getHeight(root.left); int rightHeight = getHeight(root.right); // Return the maximum height between left and right // subtrees + 1 for the current node return 1 + Math.max(leftHeight, rightHeight); } // Function to count paths in the tree where node values // form a triangular number sequence static int countTriPath(Node root, int ind, List<Integer> triNum, int count) { // Base case: // If the current node is NULL or its value does not // match the triangular number at index 'ind' if (root == null || !(triNum.get(ind) == root.data)) { return count; // Return the current count } // Check if the current node is a leaf node if (root.left == null && root.right == null ) { // Increment count as it forms a valid path count++; } // Recursive call to explore left subtree and right // subtree count = countTriPath(root.left, ind + 1 , triNum, count); return countTriPath(root.right, ind + 1 , triNum, count); } // Function to count paths in the tree where node values // form a triangular number sequence static int countTriangularNumberPath(Node root) { // Get the height of the tree int n = getHeight(root); List<Integer> triNum = new ArrayList<>(); int currentLevel = 1 ; int triangularNumber = 0 ; // Generating the triangular number sequence based // on tree height for ( int i = 1 ; i <= n; i++) { // Add the current level to the triangular // number triangularNumber += currentLevel; triNum.add(triangularNumber); // Incrementing current level currentLevel++; } // Call the function to count paths satisfying the // triangular number sequence condition int cntPath = countTriPath(root, 0 , triNum, 0 ); return cntPath; } // Driver code public static void main(String[] args) { // Example tree creation Node root = new Node( 1 ); root.left = new Node( 3 ); root.right = new Node( 3 ); root.left.left = new Node( 2 ); root.left.right = new Node( 5 ); root.right.left = new Node( 6 ); root.right.right = new Node( 7 ); root.right.left.right = new Node( 10 ); // Finding the number of paths and printing the // result int ans = countTriangularNumberPath(root); System.out.println(ans); } } // This code is contributed by Susobhan Akhuli |
Python3
# Python program for the above approach # Build tree class class Node: def __init__( self , val): self .data = val self .left = None self .right = None # Function to find the height of the given tree def get_height(root): # Base case: if the root is NULL, the height is 0 if root is None : return 0 # Recursive calls to find height of left and right subtrees left_height = get_height(root.left) right_height = get_height(root.right) # Return the maximum height between left and right subtrees + 1 for the current node return 1 + max (left_height, right_height) # Function to count paths in the tree where node values form a triangular number sequence def count_tri_path(root, ind, tri_num, count): # Base case: # If the current node is NULL or its value does not match the triangular number at index 'ind' if root is None or tri_num[ind] ! = root.data: return count # Return the current count # Check if the current node is a leaf node if root.left is None and root.right is None : # Increment count as it forms a valid path count + = 1 # Recursive call to explore left subtree and right subtree count = count_tri_path(root.left, ind + 1 , tri_num, count) return count_tri_path(root.right, ind + 1 , tri_num, count) # Function to count paths in the tree where node values form a triangular number sequence def count_triangular_number_path(root): # Get the height of the tree n = get_height(root) tri_num = [] current_level = 1 triangular_number = 0 # Generating the triangular number sequence based on tree height for i in range ( 1 , n + 1 ): # Add the current level to the triangular number triangular_number + = current_level tri_num.append(triangular_number) # Incrementing current level current_level + = 1 # Call the function to count paths satisfying the triangular number sequence condition cnt_path = count_tri_path(root, 0 , tri_num, 0 ) return cnt_path # Driver code if __name__ = = "__main__" : # Example tree creation root = Node( 1 ) root.left = Node( 3 ) root.right = Node( 3 ) root.left.left = Node( 2 ) root.left.right = Node( 5 ) root.right.left = Node( 6 ) root.right.right = Node( 7 ) root.right.left.right = Node( 10 ) # Finding number of paths and printing the result ans = count_triangular_number_path(root) print (ans) # This code is contributed by Susobhan Akhuli |
C#
// C# program for the above approach using System; using System.Collections.Generic; // Build tree class class Node { public int data; public Node left; public Node right; public Node( int val) { data = val; left = null ; right = null ; } } class MainClass { // Function to find the height of the given tree static int GetHeight(Node root) { // Base case: if the root is NULL, the height is 0 if (root == null ) return 0; // Recursive calls to find height of left and right // subtrees int leftHeight = GetHeight(root.left); int rightHeight = GetHeight(root.right); // Return the maximum height between left and right // subtrees + 1 for the current node return 1 + Math.Max(leftHeight, rightHeight); } // Function to count paths in the tree where node values // form a triangular number sequence static int CountTriPath(Node root, int ind, List< int > triNum, int count) { // Base case: If the current node is NULL or its // value does not match the triangular number at // index 'ind' if (root == null || !(triNum[ind] == root.data)) { return count; // Return the current count } // Check if the current node is a leaf node if (root.left == null && root.right == null ) { // Increment count as it forms a valid path count++; } // Recursive call to explore left subtree and right // subtree count = CountTriPath(root.left, ind + 1, triNum, count); return CountTriPath(root.right, ind + 1, triNum, count); } // Function to count paths in the tree where node values // form a triangular number sequence static int CountTriangularNumberPath(Node root) { // Get the height of the tree int n = GetHeight(root); List< int > triNum = new List< int >(); int current_level = 1; int triangular_number = 0; // Generating the triangular number sequence based // on tree height for ( int i = 1; i <= n; i++) { // Add the current level to the triangular // number triangular_number += current_level; triNum.Add(triangular_number); // Incrementing current level current_level++; } // Call the function to count paths satisfying the // triangular number sequence condition int cntPath = CountTriPath(root, 0, triNum, 0); return cntPath; } // Driver code public static void Main( string [] args) { // Example tree creation Node root = new Node(1); root.left = new Node(3); root.right = new Node(3); root.left.left = new Node(2); root.left.right = new Node(5); root.right.left = new Node(6); root.right.right = new Node(7); root.right.left.right = new Node(10); // Finding number of paths and printing the result int ans = CountTriangularNumberPath(root); Console.WriteLine(ans); } } // This code is contributed by Susobhan Akhuli |
Javascript
// javaScript code for the above approach // Node class to build the tree structure class Node { constructor(val) { this .data = val; this .left = null ; this .right = null ; } } // Function to find the height of the tree function getHeight(root) { if (!root) return 0; const leftHeight = getHeight(root.left); const rightHeight = getHeight(root.right); return 1 + Math.max(leftHeight, rightHeight); } // Function to count paths in the tree where // node values form a triangular number sequence function cntTriPath(root, ind, triNum, count) { if (!root || triNum[ind] !== root.data) { return count; } if (!root.left && !root.right) { count++; } count = cntTriPath(root.left, ind + 1, triNum, count); return cntTriPath(root.right, ind + 1, triNum, count); } // Function to count paths in the tree where // node values form a triangular number sequence function CountTriangularNumberPath(root) { const n = getHeight(root); const triNum = []; let currentLevel = 1; let triangularNumber = 0; for (let i = 1; i <= n; i++) { triangularNumber += currentLevel; triNum.push(triangularNumber); currentLevel++; } const cntPath = cntTriPath(root, 0, triNum, 0); return cntPath; } // Example tree creation let root = new Node(1); root.left = new Node(3); root.right = new Node(3); root.left.left = new Node(2); root.left.right = new Node(5); root.right.left = new Node(6); root.right.right = new Node(7); root.right.left.right = new Node(10); // Finding number of paths and // printing the result let ans = CountTriangularNumberPath(root); console.log(ans); |
1
Time Complexity: O(N), Where N is the number of nodes in the given tree.
Auxiliary Complexity: O(H), Where H is the height of the tree.
Contact Us