Untitled

mail@pastecode.io avatar
unknown
typescript
6 months ago
1.5 kB
3
Indexable
Never
class NodeItem {
  left: NodeItem | null;
  right: NodeItem | null;
  value: number;

  constructor(left: NodeItem | null, right: NodeItem | null, value: number) {
    this.left = left;
    this.right = right;
    this.value = value;
  }
}

function findEdges(root: NodeItem | null) {
  if (!root) {
    return [];
  }

  const rootVal = root.value;

  const leftStore = findEdgesLeft(root.left, [], 0);
  const rightStore = findEdgesRight(root.right, [], 0);

  return [
    ...leftStore.reverse().map((node) => node.value),
    rootVal,
    ...rightStore.reverse().map((node) => node.value),
  ];
}

function findEdgesLeft(node: NodeItem | null, store: NodeItem[], position = 0) {
  if (!node) {
    return store;
  }

  if (!store[position]) {
    store.push(node);
  }

  store = findEdgesLeft(node.left, store, position + 1);

  if (position > 0) {
    store = findEdgesLeft(node.right, store, position - 1);
  }

  return store;
}

function findEdgesRight(
  node: NodeItem | null,
  store: NodeItem[],
  position = 0,
) {
  if (!node) {
    return store;
  }

  if (!store[position]) {
    store.push(node);
  }

  store = findEdgesRight(node.right, store, position + 1);

  if (position > 0) {
    store = findEdgesRight(node.left, store, position - 1);
  }

  return store;
}

const eight = new NodeItem(null, null, 8);
const seven = new NodeItem(null, eight, 7);
const two = new NodeItem(null, null, 2);
const six = new NodeItem(null, two, 6);
const root = new NodeItem(seven, six, 4);

console.log(findEdges(root));