Ah the classic interview question. Recurse Binary Trees. I don't know why they just love to give this one but I have some time off so I thought I would solve it. This is for a github project where I will point interviewers at so maybe they will just believe I can do this stuff.
The key to this is to check the other node in the recursion of the find or it will go down the right or left leg and get lost. There are some good Data Structures articles on BTS that I used to come to this solution. Here you go:
- http://cslibrary.stanford.edu/110/BinaryTrees.html
- http://opendatastructures.org/ods-java/6_1_BinaryTree_Basic_Binary.html
This file contains 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
| /** | |
| * will return a null value if a match cant be found. You have to search | |
| * both ways or it will get lost on the right or left directions. This is | |
| * a classic "gotcha" | |
| * | |
| * @param root | |
| * @param nodeId | |
| * @return | |
| */ | |
| public BinaryTreeNode searchNodeById(BinaryTreeNode root, Integer nodeId){ | |
| if(root.getId().equals(nodeId)) { | |
| return root; | |
| } else if (root.getLeft() != null) { | |
| BinaryTreeNode node = searchNodeById(root.getLeft(),nodeId); | |
| if(node == null){ | |
| return searchNodeById(root.getRight(),nodeId); | |
| } else { | |
| return node; | |
| } | |
| } else if (root.getRight() != null) { | |
| BinaryTreeNode node = searchNodeById(root.getRight(),nodeId); | |
| if(node == null){ | |
| return searchNodeById(root.getLeft(),nodeId); | |
| } else { | |
| return node; | |
| } | |
| } else { | |
| return null; | |
| } | |
| } |
