Longest path with same values in a binary tree

calvinfornia (48)
Hi, here's a source code of a program working on the longest path with same values in a binary tree.

Given a binary tree, find the length of the longest path where each node in the path has the same value. This path may or may not pass through the root. The length of path between two nodes is represented by the number of edges between them.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
 
// C++ program to find the length of longest 
// path with same values in a binary tree. 
#include <bits/stdc++.h> 
using namespace std; 
  
/* A binary tree node has data, pointer to 
left child and a pointer to right child */
struct Node { 
  int val; 
  struct Node *left, *right; 
}; 
  
/* Function to print the longest path 
   of same values */
int length(Node *node, int *ans) { 
  if (!node) 
    return 0; 
  
  // Recursive calls to check for subtrees 
  int left = length(node->left, ans); 
  int right = length(node->right, ans); 
  
  // Variables to store maximum lengths in two directions 
  int Leftmax = 0, Rightmax = 0; 
  
  // If curr node and it's left child has same value 
  if (node->left && node->left->val == node->val)  
    Leftmax += left + 1;   
  
  // If curr node and it's right child has same value 
  if (node->right && node->right->val == node->val)  
    Rightmax += right + 1; 
    
  *ans = max(*ans, Leftmax + Rightmax); 
  return max(Leftmax, Rightmax); 
} 
  
/* Driver function to find length of 
   longest same value path*/
int longestSameValuePath(Node *root) { 
  int ans = 0; 
  length(root, &ans); 
  return ans; 
} 
  
/* Helper function that allocates a 
new node with the given data and 
NULL left and right pointers. */
Node *newNode(int data) { 
  Node *temp = new Node; 
  temp->val = data; 
  temp->left = temp->right = NULL; 
  return temp; 
} 
  
// Driver code 
int main() { 
  /* Let us construct a Binary Tree 
        4 
       / \ 
      4   4 
     / \   \ 
    4   9   5 */
  
  Node *root = NULL; 
  root = newNode(4); 
  root->left = newNode(4); 
  root->right = newNode(4); 
  root->left->left = newNode(4); 
  root->left->right = newNode(9); 
  root->right->right = newNode(5); 
  cout << longestSameValuePath(root); 
  return 0; 
}


My question is in line 26, 27 
1
2
 
// If curr node and it's left child has same value 
  if (node->left && node->left->val == node->val)

Why isn't is 
1
2
 
// If curr node and it's left child has same value 
  if (node->left->val == node->val)
if it want to determine whether current node and it's left child has same value.

Why do we need the first term in the parathesis
node->left
Last edited on
Repeater (3046)
What happens if node->left is NULL?
node->left->val will crash, that's what.

How do we protect against that?
By checking if node->left is NULL before we try to use it

How do we check for a NULL pointer?
1
2
 
 if (node->left &&   // FALSE if node->left == NULL
     node->left->val == node->val)
calvinfornia (48)
Got it ! Thanks a lot !
Topic archived. No new replies allowed.