## Apple Interview Question

Software Engineers**Country:**United States

```
public String bstSearch(TreeNode<Integer> node , int num){
if (node == null){
return "NotFound";
}
if (node.val == num){
return "Undefined";
}
String str = bst(node, num);
return str;
}
public String bst(TreeNode<Integer> node, int num){
if (node == null){
return "NotFound";
}
if (node.val == num){
return "found";
}
if (num < node.val){
String str1 = bst(node.left, num);
if (str1.equals("NotFound")){
return str1;
}
else if (str1.equals("found")){
return "0";
}
else {
return "0"+str1;
}
}
if (num > node.val){
String str1 = bst(node.right, num);
if (str1.equals("NotFound")){
return str1;
}
else if (str1.equals("found")){
return "1";
}
else {
return "1"+str1;
}
}
return null;
}
class TreeNode<T> {
T val;
TreeNode left;
TreeNode right;
TreeNode(T x) { val = x; }
}
```

Solution in python

```
class node(object):
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def buildABCString(root, value):
res = ""
if root.value == value: return "Undefined"
node = root
while node != None:
if node.value == value: return res
elif value > node.value:
res += "1"
node = node.right
else:
res += "0"
node = node.left
return "Not Found"
```

```
public String bstNotation(int num) {
if (root == null) return "Not Found";
Node curr = root;
StringBuilder notation = new StringBuilder();
if(root.data==num)
return "Undefined";
while (curr != null) {
if (num<curr.data) {
curr = curr.left;
notation.append("0");
} else if (num>curr.data) {
curr = curr.right;
notation.append("1");
} else if (num==curr.data) {
return notation.toString();
}
}
return "Not Found";
}
```

Not exactly proud of it, but:

- NoOne June 17, 2017