Created
April 6, 2023 09:48
-
-
Save devaman/6968a88341a3aefa33ddc60aea003272 to your computer and use it in GitHub Desktop.
binary search tree Javascript
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // Definition for a binary tree node. | |
| function TreeNode(val, left, right) { | |
| this.val = (val===undefined ? 0 : val) | |
| this.left = (left===undefined ? null : left) | |
| this.right = (right===undefined ? null : right) | |
| } | |
| /** | |
| * @param {number[]} nums | |
| * @return {TreeNode} | |
| */ | |
| const printTree = (tree) =>{ | |
| let queue = [tree] | |
| let height = 1 | |
| while(queue.length){ | |
| let next =[] | |
| let cals = queue.reduce((acc,curr)=>{ | |
| acc= acc + ' '.repeat(40-height*10)+ curr.val | |
| return acc | |
| },'') | |
| console.log(cals); | |
| while(queue.length) { | |
| let val = queue.splice(0,1)[0] | |
| if(val.left) next.push(val.left) | |
| if(val.right) next.push(val.right) | |
| } | |
| if(next.length) { | |
| queue = next | |
| height++ | |
| } | |
| } | |
| } | |
| var sortedArrayToBST = function(nums) { | |
| return createBst(nums, 0, nums.length-1) | |
| }; | |
| const createBst= (arr, left, right) => { | |
| if(left>right) return null | |
| const mid = Math.ceil((left+right)/2) | |
| const root = new TreeNode(arr[mid]) | |
| root.left = createBst(arr,left, mid-1) | |
| root.right = createBst(arr, mid+1, right) | |
| return root | |
| } | |
| const search = (bst, val)=>{ | |
| if(bst.val === null) return null | |
| if(bst.val === val) return bst | |
| else if(bst.val > val) return search(bst.left, val) | |
| else return search(bst.right, val) | |
| } | |
| let a = [-1,0,2,3,6,10,20] | |
| let tree = sortedArrayToBST(a) | |
| printTree(tree) | |
| printTree(search(tree,2)) | |
| // console.log(JSON.stringify(tree)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment