aboutsummaryrefslogtreecommitdiff
path: root/validate_bst_node.c
blob: 160b33f3d20d95b65c7ab6b89eebbadfbf8db6f0 (plain)
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
75
76
77
// 1361. Validate Binary Tree Nodes
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

/*
 * you have n binary trees nodes numbered from 0 to n - 1 where node i has two
 * children left_child and right_child. return true if any only if all the given
 * nodes from exactly one valid binary tree. if node i has no left children,
 * then left_child[i] will equal -1. note that the nodes have no values and that
 * we only use the node numbers in this problem.
 */

bool validateBinaryTreeNodes(int n, int *left_child, int left_child_size,
                             int *right_child, int right_child_size) {
  bool *flag = calloc(n, sizeof(bool));
  for (int i = 0; i < n; i++) {
    if (left_child[i] == -1)
      continue;
    flag[left_child[i]] = true;
  }
  for (int i = 0; i < n; i++) {
    if (right_child[i] == -1)
      continue;
    flag[right_child[i]] = true;
  }
  int root = -1;
  for (int i = 0; i < n; i++) {
    if (!flag[i]) {
      if (root == -1)
        root = i;
      else
        return false;
    }
  }
  if (root == -1)
    return false;
  bool *visited = calloc(n, sizeof(bool));
  int *stack = malloc(2 * n * sizeof(int));
  int count = 0;
  stack[count] = root;
  count++;
  int p = 0, node = 0;

  while (p < count) {
    node++;
    int left = left_child[stack[p]];
    int right = right_child[stack[p]];
    visited[stack[p]] = true;
    p++;
    if (left != -1) {
      if (visited[left] == true)
        return false;
      stack[count] = left;
      count++;
    }
    if (right != -1) {
      if (visited[right] == true)
        return false;
      stack[count] = right;
      count++;
    }
  }
  free(flag), free(visited);
  if (node == n)
    return true;
  return false;
}

int main() {
  int lc1[] = {1, -1, 3, -1}, rc1[] = {2, -1, -1, -1};
  int lc2[] = {1, -1, 3, -1}, rc2[] = {2, 3, -1, -1};
  int lc3[] = {1, 0}, rc3[] = {-1, -1};
  printf("%d\n", validateBinaryTreeNodes(4, lc1, 4, rc1, 4)); // expect: 1
  printf("%d\n", validateBinaryTreeNodes(4, lc2, 4, rc2, 4)); // expect: 0
  printf("%d\n", validateBinaryTreeNodes(2, lc3, 2, rc3, 2)); // expect: 0
}