This is my implementation of a red-black tree that I'm planning to use in a little personal project. It works fine, however I'm not sure that the code is very good as I'm only a beginner, and insertions are 4x slower than in a broken implementation I found here (it stops working after a few insertions). I was wondering if I did something unnecessary that slows down the algorithm or is it just because my nodes also have keys instead of just data. I'd greatly appreciate any suggestions and corrections. ``` enum Color { Red = 0, Black }; template class RBTree { public: RBTree(); ~RBTree(); void Insert(TKey Key, TData Data); void Delete(TKey Key); TData * Find(TKey Key); private: struct Node { Node(const TKey & Key, const TData & Data, Node * Parent); ~Node(); Color _Color; Node * _Link[2]; Node * _Parent; TKey _Key; TData _Data; }; Node * _Root; }; template inline RBTree::RBTree() : _Root(nullptr) { } template inline RBTree::~RBTree() { delete _Root; } template inline void RBTree::Insert(TKey Key, TData Data) { Node * pNode = nullptr; Node * pParent = nullptr; Node * pUncle = nullptr; Node * pGrandparent = nullptr; Node * T = nullptr; int Dir; int PDir; if (!_Root) { _Root = new Node(Key, Data, nullptr); _Root->_Color = Black; } else { pNode = _Root; while (pNode) { pParent = pNode; Dir = Key > pNode->_Key; pNode = pNode->_Link[Dir]; } pParent->_Link[Dir] = new Node(Key, Data, pParent); pNode = pParent->_Link[Dir]; TKey k; TData d; Node * n; while (pNode->_Parent && pNode->_Parent != _Root && pParent->_Color == Red) { pGrandparent = pParent->_Parent; PDir = pParent->_Data > pGrandparent->_Data; pUncle = pGrandparent->_Link[!PDir];

In an interview I was asked to write Java code to build a tree and return the root, given a list of edges. It was a fairly open ended question where the interviewer left all the decisions up to me. I used to following logic: edges of trees are directional, so I made a Pair class which has a start node and an end node. I go over the list of Pairs and I made a HashMap from it in a way that the each key in the map is kept as a node and then the value in the map is the set of its children. Then for each key I iterate over the sets of children and see if that node is a child of any other node. If it is then it is not the node we are looking for, if a node isn't in any children set then it is the root. There are of course edge cases where there can be a cycle within the tree, so let's say some node connects to the root. Or another case is that the root might be fine, but there are cycles within the children nodes. Or there is another case where there can be multiple distinct trees in the list of edges. I tried to code this up in the following manner and I have tried to add comments wherever applicable so that the code can be understood more: ``` import java.util.*; public class TreeBuilder { public static Node returnRoot(List input){ if(input == null || input.size() == 0){ throw new IllegalArgumentException("Input is null or doesn't contain any elements"); } // Create a list of roots, in case there are multiple roots present List roots = new ArrayList<>(); // This boolean checks if there are edges pointing to a particular node boolean isPresent = false; HashMap> adjList = buildList(input); // iterate over each key of the hash map (which is the tree) and check if there are any edges pointing to it for(Node keyItr: adjList.keySet()) { for (HashSet setItr : adjList.values()) { if (setItr.contains(keyItr)) {

I need to calculate the height of an optional (not AVL, binary) tree. For input I receive an `n` integer positive number: `parent(0)`, `parent(1)`, ... `parent(n-1)`. Here, `parent(i)` is a parent of node `i`. If `parent(i) == -1`, that `i` is the root of the tree. It is guaranteed that the sequence has only one root and presets a tree. Limitation: \$1 \le n \le 1e5\$ Example input: ``` 5 4 -1 4 1 1 ``` Output: ``` 3 1 / \ 3 4 /\ 0 2 ``` My program on C++ works but it looks like that the algorithm is not optimal. The program is verified automatically and one of the test failed with error "Time limit exceeded". Could you advise me, please, on how I can optimize the program? ``` #include "iostream" int tree[10000]; int n = 0; int Height(int parent); int main () { std::cin >> n; for (int i = 0; i > tree[i]; } std::cout << Height(-1) - 1; return 0; } int Height(int parent) { int height = 1; for (int i = 0; i < n; ++i) { if (tree[i] == parent) { height = std::max(height, 1 + Height(i)); } } return height; } ```

I had this question asked in an interview: In how many ways, we can construct binary search tree from \$n\$ elements? I have written this code, but got a feedback that it could be improved. How to do it? ``` def count_ways(n): c = [0] * (n+1) c[0] = 1 c[1] = 1 for i in xrange(2, n+1): sum_w = 0 for j in xrange(0, i): sum_w += c[j] * c[i-j-1] c[i] = sum_w return c[n] print count_ways(4) ```

Today I had an interview where I was asked to solve "Given an binary tree, convert it to binary search tree in minimum time, space complexity". I wrote this code, but got the feedback that complexity could be improved without using sort and without using external storage. How to do it? ``` ##code goes below##: class Node: def __init__(self, data): self.data = data self.left = None self.right = None def inorder(root,arr): if root is None: return inorder(root.left, arr) arr.append(root.data) inorder(root.right, arr) def binary_to_bst(root, arr): if root is None: return binary_to_bst(root.left, arr) root.data = arr.pop(0) binary_to_bst(root.right, arr) root = Node(4) root.left = Node(2) root.right = Node(1) root.left.left = Node(5) root.left.right = Node(7) root.right.left = Node(12) arr = [] inorder(root,arr) arr.sort() binary_to_bst(root, arr) ```

this is the first time I' implementing a Trie. My goal was to make it as simple as possible. So here is the result: Can I simplify anything else? Are there some things I can change to increase performance ? Also any feedback on code quality/design is welcome :) Node.java ``` package trie; public class Node { final Node[] children = new Node[26]; boolean isEnd = false; } ``` Trie.java ``` package trie; import java.util.ArrayList; import java.util.List; public class Trie { static final int ALPHABET_SIZE = 26; final Node root = new Node(); void add(String str) { Node curr = root; for (int i = 0; i prefixedWords(String str) { Node curr = getNode(str); List prefixedWords = new ArrayList<>(); DFS(curr, str, prefixedWords); return prefixedWords; } void DFS(Node root, String prefix, List list) { if (root != null) { if (root.isEnd) { list.add(prefix); } for (int i = 0; i < ALPHABET_SIZE; i++) { if (root.children[i] != null) { DFS(root.children[i], prefix + (char) (i + 'a'), list); } } } } } ```

I have implemented a tree in Python. However, due to my lack of experience with Python, I am not able to judge the overall quality of my code. ``` import unittest from datetime import * from gc import * RET_NO = 0 RET_YES = 1 RET_MAYBE = 0.5 # haha :) class Tree(object): """ Mutable abstract data type for arbitrary data with O(N) access on elements. """ def __init__(self): super(Tree, self).__init__() self.root = None def insert(self, element): if self.root: self.root.insert(element) else: self.root = Node(element) def contains(self, element): if self.root is None: print 'WARN: Contains() called before elements were inserted!!' raise Exception() return self.root.contains(element) if self.root else RET_NO def size(self): return self.root.size() if self.root else 0 def bulk_insert(self, elements=[]): while len(elements): self.insert(element[0]) elements = elements[1:] class Node(object): """ Node class to be used in Tree instances. """ def __init__(self, element): super(Node, self).__init__() self.element = element self.left = None self.right = None def insert(self, element): if self.element == element: return if element test failed self.assertTrue(False) except Exception, ValueError: # expected to raise an Exception -> test should pass self.assertTrue(True) ```

I am learning C++ and today I've implemented a version of the binary search tree. I would like your thoughts about it. node.h ``` #pragma once struct Node { int val; Node *left; Node *right; }; ``` bTree.h ``` #include "node.h" #pragma once class BTree { private: Node *root; void addValue(int n, Node *node); void traverse(Node *node); Node* search(int n, Node *node); public: BTree(); void addValue(int n); void traverse(); void search(int n); }; ``` bTree.cpp ``` #include #include "bTree.h" BTree::BTree() { root = nullptr; } void BTree::addValue(int n, Node *node) { if (n val) { if (node->left != nullptr) { addValue(n, node->left); } else { node->left = new Node; node->left->val = n; node->left->left = nullptr; node->left->right = nullptr; } } else if (n >= node->val) { if (node->right != nullptr) { addValue(n, node->right); } else { node->right = new Node; node->right->val = n; node->right->left = nullptr; node->right->right = nullptr; } } } void BTree::traverse(Node *node) { if (node->left != nullptr) traverse(node->left); std::cout val right != nullptr) traverse(node->right); } Node* BTree::search(int n, Node *node) { if (node != nullptr) { if (node->val == n) return node; else if (n val) return search(n, node->left); else if (n > node->val) return search(n, node->right); } else return nullptr; } void BTree::addValue(int n) { if (root == nullptr) { root = new Node; root->val = n; root->left = nullptr; root->right = nullptr; } else { addValue(n, root); } } void BTree::traverse() { if (root ==

I have created a C++11 implementation of a simple Tree for an online code challenge, I'd like to know how to improve it and how to make my code use less memory : ``` #include #include #include #include #include #include template class TreeNode : public std::enable_shared_from_this> { public: TreeNode(T data = T(), std::weak_ptr> parent = std::weak_ptr>()); T getData() const; void setData(const T& data); TreeNode& addChild(const T& data); TreeNode& addChild(std::shared_ptr> ptr); void removeChild(size_t indx); void removeChild(std::shared_ptr> ptr); const std::shared_ptr > findChild(const T& data) const; std::shared_ptr > findChild(const T& data); std::shared_ptr > getChild(size_t indx) const; std::shared_ptr> getChild(size_t indx); const std::weak_ptr> getParent() const; std::weak_ptr> getParent(); void changeParent(std::weak_ptr> parent); bool hasChild(const T& data) const { return findChild(data) != nullptr; } size_t getNumChildren() const; void print() const; private: T m_data {}; std::weak_ptr> m_parent { nullptr }; std::vector>> m_children {}; }; template void TreeNode::changeParent(std::weak_ptr> parent) { parent.lock()->addChild(this->shared_from_this()); m_parent.lock()->removeChild(this->shared_from_this()); m_parent = parent; } template TreeNode::TreeNode(T data, std::weak_ptr> parent) : m_parent(parent) { m_data = data; } template T TreeNode::getData() const { return m_data; } template void TreeNode::setData(const T& data) { m_data = data; } template TreeNode& TreeNode::addChild(const T& data) { m_children.push_back(std::make_shared>(data, this->shared_from_this())); return *m_children.back(); } template TreeNode& TreeNode::addChild(std::shared_ptr> ptr) { m_children.push_back(ptr); return *m_ch

I implemented code logic provided in the EPI book to determine if a binary tree is a BST. There were two approaches, therefore I used polymorphism for the common parts. I'm also using templates. I would appreciate code review on my use of smart pointers? Anything that I should have been doing that I'm not. I did not defined any destructors, should I? ``` #include #include #include #include using namespace std; template class BinarySearchNode { public: unique_ptr> leftChild; unique_ptr> rightChild; BinarySearchNode(T pData) : data(pData), leftChild(nullptr), rightChild(nullptr) {} BinarySearchNode(T pData, unique_ptr> pLeft, unique_ptr> pRight) : data(pData),leftChild(move(pLeft)), rightChild(move(pRight)) {} T getData() const { return data; }; private: T data; }; template class BSTSolution { protected: virtual bool isBSTValid(unique_ptr> const &node,T min, T max) = 0; public: bool isBinaryTreeValidBinaryTree(unique_ptr> const &root){ if(root == nullptr) return false; return isBSTValid(root, numeric_limits::min(), numeric_limits::max()); } }; template class BSTRecursiveSolution : public BSTSolution { protected: bool isBSTValid(unique_ptr> const &node,T min, T max) { if(node == nullptr) { return true; }; if(node->getData() getData() > max) { return false; } if(!isBSTValid(node->leftChild, min, node->getData()) || !isBSTValid(node->rightChild, node->getData(), max)) { return false; } return true; } }; template class BFSSolution : public BSTSolution { struct QEntry { const unique_ptr>& node; T min; T max; }; protected: bool isBSTValid(unique_ptr> const &node,T min, T max) { queue tempQueue; tempQueue.emplace(QEntry{node,min,max}); while (!tempQueue.empty()) { auto const current = tempQueue.f