aboutsummaryrefslogtreecommitdiff
path: root/vertical_order_bst.c
blob: 6f6e221dbd0bd3ad0abe227fae0fd07cc8eda6b1 (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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
// 987. Vertical Order Traversal of a Binary Tree
#include "leetcode.h"

/*
 * given the 'root' of a binary tree, calcuate the vertical order traversal of
 * the binary tree. for each node at position '(row, col)', its left and right
 * children will be at positions '(row + 1, col - 1)' and '(row + 1, col + 1)'
 * respectively. the root of the tree is at '(0, 0)'. the vertical order
 * traversal of a binary tree is a list of top to bottom ordering for each
 * column index starting from the leftmost column and ending on the rightmost
 * column. there may be multiple nodes in the same row and same column. in such
 * a case, sort these nodes by their values. return the vertical order traversal
 * of the binary tree
 */

struct value {
  int row;
  int col;
  int val;
};

int value_cmp(const void *left, const void *right) {
  const struct value *l = (const struct value *)left;
  const struct value *r = (const struct value *)right;
  return l->col < r->col ? -1 : 1;
  return l->row < r->row ? -1 : 1;
  return l->val - r->val;
}

void helper(struct TreeNode *root, int row, int col, struct value **values,
            size_t *values_size, size_t *values_cap) {
  if (root) {
    if (*values_size == *values_cap) {
      *values_cap = (*values_cap) ? *values_cap * 2 : 16;
      *values =
          (struct value *)realloc(*values, *values_cap * sizeof(struct value));
    }
    (*values)[(*values_size)].col = col;
    (*values)[(*values_size)].row = row;
    (*values)[(*values_size)].val = root->val;
    ++*values_size;
    helper(root->left, row + 1, col - 1, values, values_size, values_cap);
    helper(root->right, row + 1, col + 1, values, values_size, values_cap);
  }
}

int **verticalTraversal(struct TreeNode *root, int *returnSize,
                        int **returnColumnSizes) {
  struct value *v = NULL;
  size_t values_size = 0, values_cap = 0;
  helper(root, 0, 0, &v, &values_size, &values_cap);
  qsort(v, values_size, sizeof(struct value), &value_cmp);
  int **ans = NULL;
  *returnColumnSizes = NULL;
  *returnSize = -1;
  size_t cap = 0, sub_cap = 0;
  int prev_col = INT_MIN;
  for (size_t i = 0; i < values_size; ++i) {
    if (v[i].col != prev_col) {
      ++(*returnSize);
      if (*returnSize == cap) {
        cap = cap ? cap * 2 : 4;
        ans = (int **)realloc(ans, cap * sizeof(int *));
        *returnColumnSizes =
            (int *)realloc(*returnColumnSizes, cap * sizeof(int));
      }
      ans[*returnSize] = NULL;
      (*returnColumnSizes)[(*returnSize)] = 0;
      sub_cap = 0;
      prev_col = v[i].col;
    }
    if ((*returnColumnSizes)[*returnSize] == sub_cap) {
      sub_cap = sub_cap ? sub_cap * 2 : 4;
      ans[*returnSize] =
          (int *)realloc(ans[*returnSize], sub_cap * sizeof(int));
    }
    ans[*returnSize][(*returnColumnSizes)[*returnSize]++] = v[i].val;
  }
  ++(*returnSize);
  free(v);
  return ans;
}

int main() {
  struct TreeNode *root = treenode_create(1);
  root->left = treenode_create(2);
  root->right = treenode_create(3);
  root->left->left = treenode_create(4);
  root->left->right = treenode_create(5);
  root->right->left = treenode_create(6);
  root->right->right = treenode_create(7);
  int returnSize, *returnColumnSizes;
  int **vt = verticalTraversal(root, &returnSize, &returnColumnSizes);
  for (int i = 0; i < returnSize; i++) {
    for (int j = 0; j < returnColumnSizes[i]; j++)
      printf("%d ", vt[i][j]); // expect: [[4],[2],[1,5,6],[3],[7]]
    printf("\n");
  }
  for (int i = 0; i < returnSize; i++)
    free(vt[i]);
  free(vt), free(returnColumnSizes);
  treenode_free(root);
}