Tag Archives: dfs

C# || Two Sum IV – How To Get Two Numbers In Binary Search Tree Equal To Target Value Using C#

The following is a module with functions which demonstrates how to get two numbers in a binary search tree equal to target value using C#.


1. Find Target – Problem Statement

Given the root of a Binary Search Tree and a target number k, return true if there exist two elements in the BST such that their sum is equal to the given target.

Example 1:

Example 1


Input: root = [5,3,6,2,4,null,7], k = 9
Output: true

Example 2:

Example 2


Input: root = [5,3,6,2,4,null,7], k = 28
Output: false


2. Find Target – Solution

The following are two solutions which demonstrates how to get two numbers in a binary search tree equal to target value.

Both solutions use a set to keep track of the items already seen.

Each time a new node is encountered, we subtract the target value from the current node value. If the difference amount from subtracting the two numbers exists in the set, a 2 sum combination exists in the tree

1. Recursive

The following solution uses Depth First Search when looking for the target value.

2. Iterative

The following solution uses Breadth First Search when looking for the target value.

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output for the example cases:


true
false

C# || Word Search – How To Search A Grid Matrix For A Target Word Using C#

The following is a module with functions which demonstrates how to search a grid matrix for a target word using C#.


1. Word Search – Problem Statement

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example 1:

Example 1


Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true

Example 2:

Example 2


Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true

Example 3:

Example 3


Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output: false


2. Word Search – Solution

The following is a solution which demonstrates how to search a grid matrix for a target word. This solution uses Depth First Search.

Depth First Search (DFS) is an algorithm for searching tree or graph data structures. It starts at the root node and explores as far as possible along each branch before backtracking.

In this problem we start at the root node and search all the possibilities at each array index until a match is found. We create a ‘visited’ array to keep track of the indexes already seen.

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output for the example cases:


true
true
false