Given a Binary Tree, the task is to find the count of diagonal paths to the leaf of a binary tree such that values of all the nodes on the same diagonal are equal.
Examples:
Input:
5 / \ 6 5 \ \ 6 5Output: 2
Explanation:
Diagonal 6 – 6 and 5 – 5 contains equal value.
Therefore, the required output is 2.Input:
5 / \ 6 5 \ \ 5 5Output: 1
Approach: The main idea is to traverse the tree diagonally using a Map. Follow the steps below to solve this problem:
- Traverse the given binary tree in a diagonal order and store the starting node of each diagonal as the key and for each key, store all the values in that diagonal in a Hashset.
- After the traversal, find the number of keys having size of the set equal to 1 and print it as the answer.
Below is the implementation of the above approach.
C++14
// C++ program of the above approach #include <bits/stdc++.h>using namespace std;struct TreeNode{ int val = 0; TreeNode *left, *right; TreeNode(int x) { val = x; left = NULL; right = NULL; }};// Function to perform diagonal// traversal on the given binary treevoid fillMap(TreeNode *root, int left, map<int, set<int>> &diag){ // If tree is empty if (!root) return; // If current diagonal is not visited if (diag[left].size() == 0) { // Update diag[left] diag[left].insert(root->val); } // Otherwise, map current node // with its diagonal else diag[left].insert(root->val); // Recursively, traverse left subtree fillMap(root->left, left + 1, diag); // Recursively, traverse right subtree fillMap(root->right, left, diag);}// Function to count diagonal// paths having same-valued nodesint sameDiag(TreeNode *root){ // Maps the values of all // nodes with its diagonal map<int, set<int>> diag; // Stores indexing of diagonal int left = 0; // Function call to perform // diagonal traversal fillMap(root, left, diag); // Stores count of diagonals such // that all the nodes on the same // diagonal are equal int count = 0; // Traverse each diagonal for(auto d : diag) { // If all nodes on the current // diagonal are equal if (diag[d.first].size() == 1) // Update count count += 1; } return count;}// Driver Codeint main(){ // Given tree TreeNode *root = new TreeNode(5); root->left = new TreeNode(6); root->right = new TreeNode(5); root->left->right = new TreeNode(6); root->right->right = new TreeNode(5); // Function call cout << sameDiag(root);}// This code is contributed by mohit kumar 29 |
Java
// Java program for above approachimport java.util.*;import java.lang.*;class GFG{ // Structure of a Node static class TreeNode { int val; TreeNode left, right; TreeNode(int key) { val = key; left = null; right = null; } }; // Function to perform diagonal // traversal on the given binary tree static void fillMap(TreeNode root, int left, Map<Integer,Set<Integer>> diag) { // If tree is empty if (root == null) return; // If current diagonal is not visited if (diag.get(left) == null) { // Update diag[left] diag.put(left, new HashSet<Integer>()); diag.get(left).add(root.val); } // Otherwise, map current node // with its diagonal else diag.get(left).add(root.val); // Recursively, traverse left subtree fillMap(root.left, left + 1, diag); // Recursively, traverse right subtree fillMap(root.right, left, diag); } // Function to count diagonal // paths having same-valued nodes static int sameDiag(TreeNode root) { // Maps the values of all // nodes with its diagonal Map<Integer, Set<Integer>> diag = new HashMap<>(); // Stores indexing of diagonal int left = 0; // Function call to perform // diagonal traversal fillMap(root, left, diag); // Stores count of diagonals such // that all the nodes on the same // diagonal are equal int count = 0; // Traverse each diagonal for(Map.Entry<Integer,Set<Integer>> d:diag.entrySet()) { // If all nodes on the current // diagonal are equal if (d.getValue().size() == 1) // Update count count += 1; } return count; } // Driver function public static void main (String[] args) { TreeNode root = new TreeNode(5); root.left = new TreeNode(6); root.right = new TreeNode(5); root.left.right = new TreeNode(6); root.right.right = new TreeNode(5); System.out.println(sameDiag(root)); }}// This code is contributed by offbeat |
Python3
# Python3 program of the above approach# Structure of a Nodeclass TreeNode: def __init__(self, val = 0, left = None, right = None): self.val = val self.left = left self.right = right# Function to count diagonal# paths having same-valued nodesdef sameDiag(root): # Maps the values of all # nodes with its diagonal diag = {} # Stores indexing of diagonal left = 0 # Function to perform diagonal # traversal on the given binary tree def fillMap(root, left): # If tree is empty if not root: return # If current diagonal is not visited if left not in diag: # Update diag[left] diag[left] = set([root.val]) # Otherwise, map current node # with its diagonal else: diag[left].add(root.val) # Recursively, traverse left subtree fillMap(root.left, left + 1) # Recursively, traverse right subtree fillMap(root.right, left) # Function call to perform # diagonal traversal fillMap(root, left) # Stores count of diagonals such # that all the nodes on the same # diagonal are equal count = 0 # Traverse each diagonal for d in diag: # If all nodes on the current # diagonal are equal if len(list(diag[d])) == 1: # Update count count += 1 return count# Driver Codeif __name__ == '__main__': # Given tree root = TreeNode(5) root.left = TreeNode(6) root.right = TreeNode(5) root.left.right = TreeNode(6) root.right.right = TreeNode(5) # Function call print(sameDiag(root)) |
Javascript
<script>// JavaScript program for above approach// Structure of a Nodeclass TreeNode{ constructor(key) { this.val=key; this.left=this.right=null; }}// Function to perform diagonal// traversal on the given binary treefunction fillMap(root,left,diag){ // If tree is empty if (root == null) return; // If current diagonal is not visited if (diag.get(left) == null) { // Update diag[left] diag.set(left, new Set()); diag.get(left).add(root.val); } // Otherwise, map current node // with its diagonal else diag.get(left).add(root.val); // Recursively, traverse left subtree fillMap(root.left, left + 1, diag); // Recursively, traverse right subtree fillMap(root.right, left, diag);}// Function to count diagonal// paths having same-valued nodesfunction sameDiag(root){ // Maps the values of all // nodes with its diagonal let diag = new Map(); // Stores indexing of diagonal let left = 0; // Function call to perform // diagonal traversal fillMap(root, left, diag); // Stores count of diagonals such // that all the nodes on the same // diagonal are equal let count = 0; // Traverse each diagonal for(let [key, value] of diag.entries()) { // If all nodes on the current // diagonal are equal if (value.size == 1) // Update count count += 1; } return count;}// Driver functionlet root = new TreeNode(5);root.left = new TreeNode(6);root.right = new TreeNode(5);root.left.right = new TreeNode(6);root.right.right = new TreeNode(5);document.write(sameDiag(root));// This code is contributed by patel2127</script> |
C#
using System;using System.Collections.Generic;public class TreeNode { public int val; public TreeNode left, right; public TreeNode(int key) { val = key; left = null; right = null; } }public class GFG{ // Function to perform diagonal // traversal on the given binary tree static void fillMap(TreeNode root, int left, Dictionary<int,HashSet<int>> diag) { // If tree is empty if (root == null) return; // If current diagonal is not visited if (!diag.ContainsKey(left)) { // Update diag[left] diag.Add(left, new HashSet<int>()); diag[left].Add(root.val); } // Otherwise, map current node // with its diagonal else diag[left].Add(root.val); // Recursively, traverse left subtree fillMap(root.left, left + 1, diag); // Recursively, traverse right subtree fillMap(root.right, left, diag); } // Function to count diagonal // paths having same-valued nodes static int sameDiag(TreeNode root) { // Maps the values of all // nodes with its diagonal Dictionary<int,HashSet<int>> diag = new Dictionary<int,HashSet<int>>(); // Stores indexing of diagonal int left = 0; // Function call to perform // diagonal traversal fillMap(root, left, diag); // Stores count of diagonals such // that all the nodes on the same // diagonal are equal int count = 0; // Traverse each diagonal foreach(KeyValuePair<int,HashSet<int>> d in diag) { // If all nodes on the current // diagonal are equal if (d.Value.Count == 1) // Update count count += 1; } return count; } // Driver function static public void Main (){ TreeNode root = new TreeNode(5); root.left = new TreeNode(6); root.right = new TreeNode(5); root.left.right = new TreeNode(6); root.right.right = new TreeNode(5); Console.WriteLine(sameDiag(root)); }} |
Output:
2
Time Complexity: O(N)
Auxiliary Space: O(N)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
