Overview of Binary Tree

⛳ Overview

Binary Tree is an important data structure, and it's widely used in BFS, DFS, DP, Back tracking, Divide and conquer algorithms.

📃 Analysis

tip

3 Tree Traversals

• Inorder: Left, Root, Right
• Preorder: Root, Left, Right
• Postorder: Left, Right,Root

Examples:

Inorder: 4 2 5 6 3 7 1
Preorder: 1 2 4 5 3 6 7
PostOrder: 4 5 2 6 7 3 1

✏ Code Editor

1. Print the level of each node

Live Editor

const res = {} function traverse(node, depth) { if(node===null) return; //console.log("node", node, "depth",depth); res[depth] = {node, depth}; traverse(node.left, depth+1); traverse(node.right, depth+1); }; const testCases=[binaryTree] render( <TestRun codeFn= {traverse} testCases={testCases} res={res} /> )

const res = {}

function traverse(node, depth) {
  if(node===null) return;
  //console.log("node", node, "depth",depth);
  res[depth] = {node, depth};
  traverse(node.left, depth+1);
  traverse(node.right, depth+1);
};

const testCases=[binaryTree]

render(
   <TestRun
    codeFn= {traverse}
    testCases={testCases}
    res={res}
  />
)

Result

Loading...

2. Print the number of leafs of each node

Live Editor

const res = {} function traverse(node, depth) { if(node===null) return 0; const leftCount= traverse(node.left, depth+1); const rightCount=traverse(node.right, depth+1); res[depth] = {node, count:leftCount+rightCount+1}; // console.log("node", node, "count",leftCount+rightCount+1); return leftCount+rightCount+1; }; const testCases=[binaryTree] render( <TestRun codeFn= {traverse} testCases={testCases} res={res} /> )

const res = {}

function traverse(node, depth) {
  if(node===null) return 0; 
  const leftCount= traverse(node.left, depth+1);
  const rightCount=traverse(node.right, depth+1);
  res[depth] = {node, count:leftCount+rightCount+1};
   // console.log("node", node, "count",leftCount+rightCount+1);
  return leftCount+rightCount+1;
};

const testCases=[binaryTree]

render(
   <TestRun
    codeFn= {traverse}
    testCases={testCases}
    res={res}
  />
)

Result

Loading...