Instantly share code, notes, and snippets.

# jiankuang/Binary Tree.md

Last active October 19, 2022 20:48
Show Gist options
• Save jiankuang/61642ed65336700a6db4975e846d8ffd to your computer and use it in GitHub Desktop.
Data Structures and Algorithms

# Binary Tree

## Traverse a Tree

``` // Definition for a binary tree node.
class TreeNode {
val: number
left: TreeNode | null
right: TreeNode | null
constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
this.val = (val===undefined ? 0 : val)
this.left = (left===undefined ? null : left)
this.right = (right===undefined ? null : right)
}
}```

### Preorder Traversal

#### Iterative solution

```function preorderTraversal(root: TreeNode | null): number[] {
let stack = root ? [root] : [];
let result = [];
while(stack.length > 0) {
const node = stack.pop();
result.push(node.val);
if(node.right) stack.push(node.right);
if(node.left) stack.push(node.left);
}
return result;
};```

### Inorder Traversal

#### Recursive solution

```function inorderTraversal(root: TreeNode | null): number[] {
let result = [];
if(root) {
if(root.left) result.push(...inorderTraversal(root.left));
result.push(root.val);
if(root.right) result.push(...inorderTraversal(root.right));
}
return result;
};```

#### Iterative solution

```function inorderTraversal(root: TreeNode | null): number[] {
let stack = [], result = [];
let node = root;
while(node || stack.length > 0) {
while(node) {
stack.push(node);
node = node.left;
}
node = stack.pop();
result.push(node.val);
node = node.right;
}
return result;
};```

### Postorder Traversal

#### Iterative solution

```function postorderTraversal(root: TreeNode | null): number[] {
let stack = root ? [root] : [];
let result = [];
while(stack.length > 0) {
const node = stack.pop();
result.unshift(node.val);
if(node.left) stack.push(node.left);
if(node.right) stack.push(node.right);
}
return result;
};```

# Dynamic Programming

## Fibonacci Number

### Top-down solution

```let F = [0,1];
function fib(n: number): number {
if(F[n]) return F[n];
if(n===0) return 0;
if(n===1) return 1;
F[n] = fib(n-2) + fib(n-1);
return F[n];
};```

### Bottom-up solution

```function fib(n: number): number {
let F = [0,1];
for(let i=2; i<=n; i++) {
F[i] = F[i-2] + F[i-1];
}
return F[n];
};```