From the course: Data Structures in JavaScript: Trees and Graphs
Join today to access over 25,500 courses taught by industry experts.
Depth-first search implementation
From the course: Data Structures in JavaScript: Trees and Graphs
Depth-first search implementation
- [Instructor] Now that we understand how DFS works for binary trees, it's time to get our hands dirty by implementing it in JavaScript. This hands-on coding exercise will reinforce how DFS explores paths and backtracks efficiently. We'll write a function called depthFirstSearch that searches for a target node. This function will take in two parameters, a root and a target, and returns a boolean of true if the target node exists in the tree or false otherwise. We will implement a recursive solution. Let's define the base case. The base cases are if the root is null, return false. If the root.val equals to the target, in other words, the current node is a node that we are looking for, return true. The recursive step would be to then recursively traverse to the left to search for the target and also recursively search for the target to the right. We then return it with left or right, where if any of the recursive functions outputs true, it will surface back up to the root. Now that I've…
Download courses and learn on the go
Watch courses on your mobile device without an internet connection. Download courses using your iOS or Android LinkedIn Learning app.